E - Chain Pass of Balls Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

N 人の選手が一列に並んでおり、左から順に 1, 2, \ldots, N の番号が付いています。

各選手 i（1 \leq i \leq N）は、以下の情報を持っています：

  • キャッチ力 D_i：この値以下のスピードのボールをキャッチできます。
  • パス範囲 [L_i, R_i]：L_i \leq i \leq R_i を満たす区間で、ボールをパスできる相手の範囲を表します。この区間には選手 i 自身の位置が必ず含まれます。

高橋君はこの選手たちに M 個のボールを投げ入れます。各ボール j（1 \leq j \leq M）は初期スピード W_j を持ち、最初に選手 T_j に渡されます。M 個のボールはそれぞれ独立に処理され、あるボールの結果が他のボールに影響することはありません。

ボールを受け取った選手は、最初にボールを受け取った選手も含めて、以下のルールに従って行動します：

選手 i がスピード W のボールを受け取ったとします（パスを繰り返す過程で W が 0 になることもあります）。

  1. W \leq D_i の場合（キャッチ）： 選手 i はそのボールをキャッチします。ボールの移動はここで終了します。
  2. W > D_i の場合（パス）： 選手 i はそのボールをキャッチできず、パスを試みます。
  • L_i = R_i = i の場合（パス範囲内に自分以外の選手がいない場合）：パスを行えず、選手 i がそのボールの最終保持者となります。ボールの移動はここで終了します。
  • それ以外の場合：選手 i のパス範囲 [L_i, R_i] に含まれる選手のうち、選手 i 自身を除いて最も番号の小さい選手にボールを渡します。このとき、ボールのスピードは 1 減少し W - 1 となります。パス先は選手 i より左（番号が小さい方）になることも右（番号が大きい方）になることもあります。

パスが左方向にも行われうるため、同じ選手を複数回訪れることがあります。ただし、パスのたびにスピードは 1 減少し、すべての選手について D_i \geq 0 であるため、各ボールについてボールの移動は必ず有限回で終了します。

M 個のボールそれぞれについて、最終的な結果を出力してください。ボールがキャッチされた場合（上記ルール 1 で終了した場合）は -1 を、最終保持者が存在する場合（上記ルール 2 の前者で終了した場合）はその選手の番号を出力してください。

制約

  • 1 \leq N, M \leq 2 \times 10^5
  • N + M \leq 2 \times 10^5
  • 0 \leq D_i \leq 10^9
  • 1 \leq L_i \leq i \leq R_i \leq N
  • 1 \leq T_j \leq N
  • 1 \leq W_j \leq 10^9
  • 入力はすべて整数である。

入力

N M
D_1 L_1 R_1
D_2 L_2 R_2
\vdots
D_N L_N R_N
T_1 W_1
T_2 W_2
\vdots
T_M W_M
  • 1 行目には、選手の人数を表す整数 N と、ボールの個数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各選手の情報が与えられる。
  • 1 + i 行目（1 \leq i \leq N）では、選手 i のキャッチ力 D_i 、パス範囲の左端 L_i 、パス範囲の右端 R_i が、スペース区切りで与えられる。L_i \leq i \leq R_i が成り立つ。
  • N + 2 行目から N + M + 1 行目では、各ボールの情報が与えられる。
  • N + 1 + j 行目（1 \leq j \leq M）では、ボール j の最初の受け取り手の選手番号 T_j と、ボール j の初期スピード W_j が、スペース区切りで与えられる。

出力

M 行出力せよ。j 行目（1 \leq j \leq M）には、ボール j がキャッチされた場合は -1 を、最終保持者が存在する場合はその選手の番号を出力せよ。

入力例 1

4 5
2 1 2
0 1 3
5 3 4
1 4 4
1 1
1 4
2 3
3 7
4 2

出力例 1

-1
-1
-1
4
4

入力例 2

3 4
10 1 1
1 1 2
0 2 3
1 10
2 2
3 2
3 1

出力例 2

-1
-1
-1
-1

入力例 3

8 10
0 1 1
3 1 2
1 2 5
4 4 6
2 3 5
0 5 8
10 7 8
1 6 8
1 5
2 4
3 2
4 6
5 5
6 3
7 11
8 2
4 4
6 1

出力例 3

1
1
-1
-1
-1
-1
1
-1
-1
-1

入力例 4

15 15
5 1 3
2 1 4
0 2 5
7 4 4
1 3 7
4 6 9
0 5 8
10 7 10
3 1 9
6 10 12
0 9 13
2 12 15
8 11 14
1 13 15
0 15 15
1 6
2 5
3 1
4 1000000000
5 9
6 6
7 2
8 11
9 4
10 20
11 3
12 5
13 9
14 2
15 1

出力例 4

-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
15

入力例 5

1 2
0 1 1
1 1
1 1000000000

出力例 5

1
1

Score : 466 pts

Problem Statement

N players are standing in a row, numbered 1, 2, \ldots, N from left to right.

Each player i (1 \leq i \leq N) has the following information:

  • Catching Power D_i: They can catch a ball with a speed less than or equal to this value.
  • Passing Range [L_i, R_i]: An interval satisfying L_i \leq i \leq R_i that represents the range of players to whom they can pass the ball. This interval always contains player i's own position.

Takahashi will throw M balls to these players. Each ball j (1 \leq j \leq M) has an initial speed W_j and is initially handed to player T_j. The M balls are processed independently, and the result of one ball does not affect any other balls.

A player who receives a ball (including the player who receives it initially) acts according to the following rules:

Suppose player i receives a ball with speed W (note that W may become 0 through repeated passes).

  1. If W \leq D_i (Catch): Player i catches the ball. The movement of the ball ends here.
  2. If W > D_i (Pass): Player i cannot catch the ball and attempts to pass it.
  • If L_i = R_i = i (i.e., there is no player other than themselves in their passing range): They cannot make a pass, and player i becomes the final holder of the ball. The movement of the ball ends here.
  • Otherwise: They pass the ball to the player with the smallest index other than player i themselves among the players in player i's passing range [L_i, R_i]. At this time, the speed of the ball decreases by 1 to become W - 1. The receiver of the pass can be either to the left (smaller index) or to the right (larger index) of player i.

Since passes can also be made to the left, the same player may be visited multiple times. However, since the speed decreases by 1 with each pass and D_i \geq 0 holds for all players, the movement of each ball is guaranteed to end after a finite number of steps.

For each of the M balls, output the final result. If the ball is caught (ends by rule 1 above), output -1. If there is a final holder (ends by the former case of rule 2 above), output the index of that player.

Constraints

  • 1 \leq N, M \leq 2 \times 10^5
  • N + M \leq 2 \times 10^5
  • 0 \leq D_i \leq 10^9
  • 1 \leq L_i \leq i \leq R_i \leq N
  • 1 \leq T_j \leq N
  • 1 \leq W_j \leq 10^9
  • All input values are integers.

Input

N M
D_1 L_1 R_1
D_2 L_2 R_2
\vdots
D_N L_N R_N
T_1 W_1
T_2 W_2
\vdots
T_M W_M
  • The first line contains an integer N, representing the number of players, and an integer M, representing the number of balls, separated by a space.
  • The next N lines, from the 2nd to the (N + 1)-th line, contain the information of each player.
  • The (1 + i)-th line (1 \leq i \leq N) contains the catching power D_i, the left end of the passing range L_i, and the right end of the passing range R_i of player i, separated by spaces. It is guaranteed that L_i \leq i \leq R_i.
  • The following M lines, from the (N + 2)-th to the (N + M + 1)-th line, contain the information of each ball.
  • The (N + 1 + j)-th line (1 \leq j \leq M) contains the initial receiver's player index T_j and the initial speed W_j of ball j, separated by a space.

Output

Print M lines. The j-th line (1 \leq j \leq M) should contain -1 if ball j is caught, and the index of the final holder if there is a final holder.

Sample Input 1

4 5
2 1 2
0 1 3
5 3 4
1 4 4
1 1
1 4
2 3
3 7
4 2

Sample Output 1

-1
-1
-1
4
4

Sample Input 2

3 4
10 1 1
1 1 2
0 2 3
1 10
2 2
3 2
3 1

Sample Output 2

-1
-1
-1
-1

Sample Input 3

8 10
0 1 1
3 1 2
1 2 5
4 4 6
2 3 5
0 5 8
10 7 8
1 6 8
1 5
2 4
3 2
4 6
5 5
6 3
7 11
8 2
4 4
6 1

Sample Output 3

1
1
-1
-1
-1
-1
1
-1
-1
-1

Sample Input 4

15 15
5 1 3
2 1 4
0 2 5
7 4 4
1 3 7
4 6 9
0 5 8
10 7 10
3 1 9
6 10 12
0 9 13
2 12 15
8 11 14
1 13 15
0 15 15
1 6
2 5
3 1
4 1000000000
5 9
6 6
7 2
8 11
9 4
10 20
11 3
12 5
13 9
14 2
15 1

Sample Output 4

-1
-1
-1
4
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
15

Sample Input 5

1 2
0 1 1
1 1
1 1000000000

Sample Output 5

1
1