← 返回题目列表

AtCoder · abc254_g

G. 电梯

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一个复杂的组成 N 10^9- 故事摩天大楼。摩天大楼已被编号 1 to N,并且楼层已编号 1 to 10^9.

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

此外,还有 M 电梯。的 i-th 电梯在楼层之间运行 B_i 和地板 摩天大楼的 C_i 摩天大楼 A_i。有了这部电梯,人们可以从 1 楼到达 x 到楼层 y 摩天大楼 A_i in |x-y| 分钟,对于每对整数 x,y 这样 B_i \le x,y \le C_i.

回答以下问题 Q 查询。

  • 判断是否可以从Floor获取 Y_i 摩天大楼 X_i 到楼层 W_i 摩天大楼 Z_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-st查询,可以到达目的地 12 分钟如下。

  • 使用电梯 1 从楼层获取 3 到楼层 9 摩天大楼 1,在 6 分钟。
  • 使用楼层的天桥 9 从摩天大楼获取 1 前往摩天大楼 3,在 1 分钟。
  • 使用电梯 3 从楼层获取 9 到楼层 14 摩天大楼 3,在 5 分钟。

对于 3-rd查询,目的地不可达,所以 应打印 -1 。


示例输入 2

1 1 1
1 1 2
1 1 1 2

示例输出 2

1