Elevators

题目描述

有一个由 $N$ 栋 $10^9$ 层摩天大楼组成的建筑群。摩天大楼编号为 $1$ 到 $N$，楼层编号为 $1$ 到 $10^9$。 从任意摩天大楼的任意楼层，都可以使用空中走廊在一分钟内到达任何其他摩天大楼的同一楼层。 此外，有 $M$ 部电梯。第 $i$ 部电梯在摩天大楼 $A_i$ 的楼层 $B_i$ 和楼层 $C_i$ 之间运行。使用这部电梯，可以在 $B_i \le x,y \le C_i$ 的任意整数 $x,y$ 之间以 $|x-y|$ 分钟的时间从摩天大楼 $A_i$ 的楼层 $x$ 到达楼层 $y$。 回答以下 $Q$ 个查询。

判定是否可以从摩天大楼 $X_i$ 的楼层 $Y_i$ 到达摩天大楼 $Z_i$ 的楼层 $W_i$，如果可以，求最短所需时间。

输入格式

输入按下述格式由标准输入提供： $N$ $M$ $Q$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\vdots$ $A_M$ $B_M$ $C_M$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$

每个查询的格式如下： $X_i$ $Y_i$ $Z_i$ $W_i$

输出格式

输出 $Q$ 行。对于第 $i$ 行，如果对于 $\mathrm{query}_i$ 目标不可达则输出 $-1$；否则输出到达所需的最少分钟数。

3 4 3
1 2 10
2 3 7
3 9 14
3 1 3
1 3 3 14
3 1 2 7
1 100 1 101

12
7
-1

1 1 1
1 1 2
1 1 1 2

1

提示

$1 \le N,M,Q \le 2 \times 10^5$ $1 \le A_i \le N$ 1 \le B_i < C_i \le 10^9 $1 \le X_i,Z_i \le N$ $1 \le Y_i,W_i \le 10^9$ 输入中的所有数值均为整数。对于第 $1$ 个查询，可以按如下方式在 $12$ 分钟内到达目的地。

使用电梯 $1$ 从摩天大楼 $1$ 的楼层 $3$ 到达楼层 $9$，耗时 $6$ 分钟。 在第 $9$ 层使用空中走廊从摩天大楼 $1$ 到摩天大楼 $3$，耗时 $1$ 分钟。 使用电梯 $3$ 从摩天大楼 $3$ 的楼层 $9$ 到达楼层 $14$，耗时 $5$ 分钟。

对于第 $3$ 个查询，目的地不可达，因此应输出 $-1$。

标签: AtCoder|abc254G

来源

AtCoder|abc254G