102546: [AtCoder]ABC254 G - Elevators

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

Problem Statement

There is a complex composed of $N$ $10^9$-story skyscrapers. The skyscrapers are numbered $1$ to $N$, and the floors are numbered $1$ to $10^9$.

From any floor of any skyscraper, one can use a skybridge to get to the same floor of any other skyscraper in one minute.

Additionally, there are $M$ elevators. The $i$-th elevator runs between Floor $B_i$ and Floor $C_i$ of Skyscraper $A_i$. With this elevator, one can get from Floor $x$ to Floor $y$ of Skyscraper $A_i$ in $|x-y|$ minutes, for every pair of integers $x,y$ such that $B_i \le x,y \le C_i$.

Answer the following $Q$ queries.

  • Determine whether it is possible to get from Floor $Y_i$ of Skyscraper $X_i$ to Floor $W_i$ of Skyscraper $Z_i$, and find the shortest time needed to get there if it is possible.

Constraints

  • $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$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$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$

Each query is in the following format:

$X_i$ $Y_i$ $Z_i$ $W_i$

Output

Print $Q$ lines. The $i$-th line should contain -1 if, for $\mathrm{query}_i$, the destination is unreachable; otherwise, it should contain the minimum number of minutes needed to get there.


Sample Input 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

Sample Output 1

12
7
-1

For the $1$-st query, you can get to the destination in $12$ minutes as follows.

  • Use Elevator $1$ to get from Floor $3$ to Floor $9$ of Skyscraper $1$, in $6$ minutes.
  • Use the skybridge on Floor $9$ to get from Skyscraper $1$ to Skyscraper $3$, in $1$ minute.
  • Use Elevator $3$ to get from Floor $9$ to Floor $14$ of Skyscraper $3$, in $5$ minutes.

For the $3$-rd query, the destination is unreachable, so -1 should be printed.


Sample Input 2

1 1 1
1 1 2
1 1 1 2

Sample Output 2

1

Input

题意翻译

有一个由 $n$ 栋大楼组成的建筑群,编号为$1,2, \dots ,n$。 从任意一栋大楼的某一层,可以使用天桥到达任意一栋楼的同一层,耗时只需要 $1$ 分钟。 另外有 $m$ 个电梯,第 $i$ 部电梯在摩天大楼 $a_i$ 的 $b_i$ 层到 $c_i$ 层这一段运行,这中间的任意一层都能到。比如当前在 $x$ 层,要去往 $y$ 层,要求 $b_i \leq x,y \leq c_i$,耗时为 $\lvert x-y \rvert$。 回答 $q$ 个询问: - 求能否从第 $x_i$ 栋楼的第 $y_i$ 层到达第 $z_i$ 栋楼的第 $w_i$ 层,如果可以,输出最短需要的时间。

Output

得分:$600$分

问题描述

有一个由$N$座$10^9$层的摩天大楼组成的建筑群。摩天大楼编号为$1$到$N$,楼层编号为$1$到$10^9$。

从任何大楼的任何楼层,都可以使用天桥在一分钟内到达任何其他大楼的相同楼层。

此外,还有$M$部电梯。第$i$部电梯在大楼$A_i$的第$B_i$层和第$C_i$层之间运行。有了这部电梯,对于每一对整数$x$和$y$,如果$B_i \le x,y \le C_i$,则可以在$|x-y|$分钟内从大楼$A_i$的第$x$层到达第$y$层。

回答以下$Q$个查询。

  • 确定是否可以从大楼$X_i$的第$Y_i$层到达大楼$Z_i$的第$W_i$层,如果可能的话,找出到达那里所需的最短时间。

约束条件

  • $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$
  • 输入中的所有值都是整数。

输入

输入以标准输入的以下格式给出:

$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$行应该包含-1,如果对于查询$\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

样例输出1

12
7
-1

对于第1个查询,你可以在12分钟内到达目的地,方法如下:

  • 使用电梯$1$从大楼$1$的第$3$层到第$9$层,耗时6分钟。
  • 在第$9$层使用天桥从大楼$1$到大楼$3$,耗时1分钟。
  • 使用电梯$3$从大楼$3$的第$9$层到第$14$层,耗时5分钟。

对于第3个查询,目的地不可达,所以应该打印-1


样例输入2

1 1 1
1 1 2
1 1 1 2

样例输出2

1

加入题单

上一题 下一题 算法标签: