B - Rolling Ball Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は、一列に並んだ M 個のマスの上でボールを転がす実験をしています。

マスには 1 から M までの番号が付けられており、マス 1 が最も高く、マス M が最も低い位置にあります。隣り合うマスの間には段差があり、マス i（ 1 \leq i \leq M - 1 ）とマス i + 1 の間の段差には、ボールが通過できる重さの閾値 W_i が定められています。重さが W_i 以上のボールはこの段差を越えてマス i+1 へ転がることができますが、重さが W_i 未満のボールはこの段差を越えることができず、そこで止まります。

高橋君は N 個のボールを使って実験を行います。ボール j（ 1 \leq j \leq N ）の重さは B_j です。各ボールについて、他のボールとは独立に以下の実験を行います。

高橋君がボール j をマス 1 に置くと、そのボールは以下のルールに従って転がります：

  1. ボールの現在のマスを p とする。初期値は p = 1 である。
  2. p < M かつ B_j \geq W_p ならば、ボールはマス p + 1 へ転がる（ p を p + 1 に更新する）。この手順を条件が満たされる限り繰り返す。
  3. p = M または B_j < W_p ならば、ボールはマス p で停止する。

各ボールについて、最終的に停止するマスの番号を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 2 \times 10^5
  • 1 \leq W_i \leq 10^9（ 1 \leq i \leq M - 1 ）
  • 1 \leq B_j \leq 10^9（ 1 \leq j \leq N ）
  • 入力はすべて整数である

入力

N M
W_1 W_2 \ldots W_{M-1}
B_1 B_2 \ldots B_N
  • 1 行目には、ボールの個数を表す整数 N とマスの個数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各段差の重さの閾値を表す M - 1 個の整数 W_1, W_2, \ldots, W_{M-1} が、スペース区切りで与えられる。
  • 3 行目には、各ボールの重さを表す N 個の整数 B_1, B_2, \ldots, B_N が、スペース区切りで与えられる。

出力

N 行出力せよ。j 行目（ 1 \leq j \leq N ）には、ボール j が最終的に停止するマスの番号を整数で出力せよ。

入力例 1

3 5
2 5 3 1
4 1 10

出力例 1

2
1
5

入力例 2

5 6
3 3 3 3 3
1 2 3 4 5

出力例 2

1
1
6
6
6

入力例 3

7 10
5 12 8 20 3 15 6 10 25
10 20 5 30 1 8 100

出力例 3

2
9
2
10
1
2
10

Score : 333 pts

Problem Statement

Takahashi is conducting an experiment rolling balls on M squares arranged in a row.

The squares are numbered from 1 to M, where square 1 is at the highest position and square M is at the lowest position. There is a step between each pair of adjacent squares, and the step between square i (1 \leq i \leq M - 1) and square i + 1 has a weight threshold W_i that determines whether a ball can pass through. A ball with weight at least W_i can roll over this step to square i+1, but a ball with weight less than W_i cannot pass this step and stops there.

Takahashi conducts the experiment using N balls. Ball j (1 \leq j \leq N) has weight B_j. For each ball, the following experiment is performed independently of the other balls.

When Takahashi places ball j on square 1, the ball rolls according to the following rules:

  1. Let p be the current square of the ball. Initially, p = 1.
  2. If p < M and B_j \geq W_p, the ball rolls to square p + 1 (update p to p + 1). This step is repeated as long as the condition is satisfied.
  3. If p = M or B_j < W_p, the ball stops at square p.

For each ball, determine the number of the square where it finally stops.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 2 \leq M \leq 2 \times 10^5
  • 1 \leq W_i \leq 10^9 (1 \leq i \leq M - 1)
  • 1 \leq B_j \leq 10^9 (1 \leq j \leq N)
  • All input values are integers

Input

N M
W_1 W_2 \ldots W_{M-1}
B_1 B_2 \ldots B_N
  • The first line contains an integer N representing the number of balls and an integer M representing the number of squares, separated by a space.
  • The second line contains M - 1 integers W_1, W_2, \ldots, W_{M-1} representing the weight thresholds of each step, separated by spaces.
  • The third line contains N integers B_1, B_2, \ldots, B_N representing the weights of each ball, separated by spaces.

Output

Print N lines. The j-th line (1 \leq j \leq N) should contain the number of the square where ball j finally stops.

Sample Input 1

3 5
2 5 3 1
4 1 10

Sample Output 1

2
1
5

Sample Input 2

5 6
3 3 3 3 3
1 2 3 4 5

Sample Output 2

1
1
6
6
6

Sample Input 3

7 10
5 12 8 20 3 15 6 10 25
10 20 5 30 1 8 100

Sample Output 3

2
9
2
10
1
2
10