/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
東西に無限に続く 1 本の大通りがあり、数直線とみなすことができます。
この大通り上で N 回道路工事が行われます。 i 番目の道路工事は時刻 S_i - 0.5 から時刻 T_i - 0.5 まで座標 X_i を通行止めにします。
Q 人の人が座標 0 に立っています。 i 番目の人は時刻 D_i に座標 0 を出発し、速度 1 で正の方向へ歩き続けます。 歩いている途中で通行止めとなっている地点に到達した場合には、そこで歩くのをやめます。
Q 人それぞれが進む距離を求めてください。
制約
- 入力は全て整数
- 1 \leq N, Q \leq 2 \times 10^5
- 0 \leq S_i < T_i \leq 10^9
- 1 \leq X_i \leq 10^9
- 0 \leq D_1 < D_2 < ... < D_Q \leq 10^9
- i \neq j かつ X_i = X_j の時、区間 [S_i, T_i) と 区間 [S_j, T_j) は重ならない
入力
入力は以下の形式で標準入力から与えられる。
N Q S_1 T_1 X_1 : S_N T_N X_N D_1 : D_Q
出力
Q 行出力せよ。
i 行目には i 番目の人が進む距離を出力せよ。 ただし i 番目の人が無限に歩き続ける場合は、代わりに -1 を出力せよ。
入力例 1
4 6 1 3 2 7 13 10 18 20 13 3 4 2 0 1 2 3 5 8
出力例 1
2 2 10 -1 13 -1
1 番目の人は時刻 0 に座標 0 を出発し、時刻 2 に座標 2 に到着した時点で、1 番目の道路工事による通行止めによって歩くのをやめます。
2 番目の人は時刻 1 に座標 0 を出発し、時刻 3 に座標 2 に到着します。この時、1 番目の道路工事は既に終了していますが、4 番目の道路工事が始まっているため、同様に座標 2 で歩くのをやめます。
4 番目および 6 番目の人は、歩いている最中に通行止めに出くわさないため、無限に歩き続けます。
Score : 500 points
Problem Statement
There is an infinitely long street that runs west to east, which we consider as a number line.
There are N roadworks scheduled on this street. The i-th roadwork blocks the point at coordinate X_i from time S_i - 0.5 to time T_i - 0.5.
Q people are standing at coordinate 0. The i-th person will start the coordinate 0 at time D_i, continue to walk with speed 1 in the positive direction and stop walking when reaching a blocked point.
Find the distance each of the Q people will walk.
Constraints
- All values in input are integers.
- 1 \leq N, Q \leq 2 \times 10^5
- 0 \leq S_i < T_i \leq 10^9
- 1 \leq X_i \leq 10^9
- 0 \leq D_1 < D_2 < ... < D_Q \leq 10^9
- If i \neq j and X_i = X_j, the intervals [S_i, T_i) and [S_j, T_j) do not overlap.
Input
Input is given from Standard Input in the following format:
N Q S_1 T_1 X_1 : S_N T_N X_N D_1 : D_Q
Output
Print Q lines. The i-th line should contain the distance the i-th person will walk or -1 if that person walks forever.
Sample Input 1
4 6 1 3 2 7 13 10 18 20 13 3 4 2 0 1 2 3 5 8
Sample Output 1
2 2 10 -1 13 -1
The first person starts coordinate 0 at time 0 and stops walking at coordinate 2 when reaching a point blocked by the first roadwork at time 2.
The second person starts coordinate 0 at time 1 and reaches coordinate 2 at time 3. The first roadwork has ended, but the fourth roadwork has begun, so this person also stops walking at coordinate 2.
The fourth and sixth persons encounter no roadworks while walking, so they walk forever. The output for these cases is -1.