D - 最寄りの消防車 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は消防指令センターのオペレーターです。管轄エリアには一直線の道路があり、その道路沿いに N 箇所の消防署があります。道路上の位置は数直線上の座標で表されます。消防署には番号 1, 2, \ldots, N が付けられており、消防署 i は座標 X_i の位置にあります。消防署の座標は X_1 < X_2 < \cdots < X_N を満たします（すなわち、番号は座標の小さい方から順に付けられています）。各消防署にはちょうど 1 台の消防車が待機しており、消防署 i の消防車の性能値は S_i です。

これから Q 件の火災通報が 1 件ずつ順番に届きます。j 番目の火災通報は座標 P_j の地点で発生した火災に対するものです。

各火災通報を受けると、その時点でまだ出動していない（待機中の）消防車の中から、以下の優先順位に従って 1 台を選び、出動させます。

  1. 火災発生地点との距離 |X_i - P_j| が最も小さい消防車を優先する。
  2. 距離が等しい消防車が複数ある場合は、その中で性能値 S_i が最も大きい消防車を優先する。
  3. 距離も性能値も等しい消防車が複数ある場合は、その中で消防署の番号 i が最も小さい消防車を優先する。

消防署の番号はすべて異なるため、上記の規則により出動する消防車は常に一意に定まります。

一度出動した消防車はその火災の消火活動に専念するため、以降の火災通報には対応できなくなります。

すべての Q 件の火災通報について、それぞれどの消防署の消防車が出動するかを求めてください。Q \leq N であることが保証されるため、待機中の消防車が足りなくなることはありません。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq N
  • 1 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • X_1 < X_2 < \cdots < X_N
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_j \leq 10^9 (1 \leq j \leq Q)
  • 入力はすべて整数である

入力

N Q
X_1 S_1
X_2 S_2
\vdots
X_N S_N
P_1
P_2
\vdots
P_Q
  • 1 行目には、消防署の数 N と火災通報の数 Q が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各消防署の情報が与えられる。
  • 1 + i 行目 (1 \leq i \leq N) には、消防署 i の座標 X_i と消防車の性能値 S_i がスペース区切りで与えられる。
  • N + 2 行目から N + 1 + Q 行目では、各火災通報の発生位置が与えられる。
  • N + 1 + j 行目 (1 \leq j \leq Q) には、j 番目の火災通報の発生座標 P_j が与えられる。

出力

Q 行出力せよ。j 行目 (1 \leq j \leq Q) には、j 番目の火災通報に対して出動する消防車が所属する消防署の番号を出力せよ。

入力例 1

3 3
2 5
5 3
8 7
5
6
1

出力例 1

2
3
1

入力例 2

5 4
1 3
3 8
5 8
7 5
9 2
4
4
8
5

出力例 2

2
3
4
1

入力例 3

8 5
100 10
200 50
400 30
500 70
600 30
800 90
900 20
1000 60
450
850
250
950
500

出力例 3

4
6
2
8
3

Score : 400 pts

Problem Statement

Takahashi is an operator at a fire command center. The jurisdiction area has a straight road, and there are N fire stations along this road. Positions on the road are represented as coordinates on a number line. The fire stations are numbered 1, 2, \ldots, N, and fire station i is located at coordinate X_i. The coordinates of the fire stations satisfy X_1 < X_2 < \cdots < X_N (that is, they are numbered in increasing order of coordinate). Each fire station has exactly one fire truck on standby, and the performance value of the fire truck at fire station i is S_i.

From now on, Q fire reports will arrive one by one in order. The j-th fire report is for a fire that occurred at coordinate P_j.

Upon receiving each fire report, one fire truck is selected from among the fire trucks that have not yet been dispatched (i.e., are still on standby) according to the following priority rules, and is dispatched:

  1. A fire truck with the smallest distance |X_i - P_j| to the fire location is preferred.
  2. If there are multiple fire trucks with the same distance, the one with the largest performance value S_i among them is preferred.
  3. If there are multiple fire trucks with the same distance and the same performance value, the one with the smallest fire station number i among them is preferred.

Since all fire station numbers are distinct, the above rules always uniquely determine which fire truck is dispatched.

Once a fire truck is dispatched, it dedicates itself to extinguishing that fire and can no longer respond to subsequent fire reports.

For all Q fire reports, determine which fire station's fire truck is dispatched. It is guaranteed that Q \leq N, so there will always be enough fire trucks on standby.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq N
  • 1 \leq X_i \leq 10^9 (1 \leq i \leq N)
  • X_1 < X_2 < \cdots < X_N
  • 1 \leq S_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq P_j \leq 10^9 (1 \leq j \leq Q)
  • All input values are integers

Input

N Q
X_1 S_1
X_2 S_2
\vdots
X_N S_N
P_1
P_2
\vdots
P_Q
  • The first line contains the number of fire stations N and the number of fire reports Q, separated by a space.
  • From the 2nd line to the (N + 1)-th line, information about each fire station is given.
  • The (1 + i)-th line (1 \leq i \leq N) contains the coordinate X_i of fire station i and the performance value S_i of its fire truck, separated by a space.
  • From the (N + 2)-th line to the (N + 1 + Q)-th line, the locations of each fire report are given.
  • The (N + 1 + j)-th line (1 \leq j \leq Q) contains the coordinate P_j of the j-th fire report.

Output

Output Q lines. The j-th line (1 \leq j \leq Q) should contain the number of the fire station to which the fire truck dispatched for the j-th fire report belongs.

Sample Input 1

3 3
2 5
5 3
8 7
5
6
1

Sample Output 1

2
3
1

Sample Input 2

5 4
1 3
3 8
5 8
7 5
9 2
4
4
8
5

Sample Output 2

2
3
4
1

Sample Input 3

8 5
100 10
200 50
400 30
500 70
600 30
800 90
900 20
1000 60
450
850
250
950
500

Sample Output 3

4
6
2
8
3