Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N 棟の 10^9 階建てのビルからなる建物があります。ビルには 1 から N の番号がついています。
任意の異なるビルの同じ階は連絡通路で結ばれているため 1 分で移動可能です。
また、M 基のエレベーターがあります。i 個目のエレベーターはビル A_i の B_i 階から C_i 階を結ぶものです。このエレベーターを使うと、B_i \le x,y \le C_i を満たす全ての整数の組 x,y に対し、ビル A_i の x 階から y 階に |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 行目には \mathrm{query}_i について、移動することが不可能であれば -1
を、そうでないならば移動時間の最小値を出力せよ。
入力例 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
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