G - Elevators Editorial /

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