Overview

Each ball stops at the cell where it first encounters an “impassable step (a step whose required weight is greater than the ball’s weight).” Thus, for each \(B_j\), the problem reduces to efficiently finding “the first \(i\) such that \(W_i > B_j\).”

Analysis

The condition for a ball to move from cell \(p\) to cell \(p+1\) is \(B_j \ge W_p\). In other words:

• Looking at \(W_1, W_2, \dots\) from left to right,
• If there exists a step \(i\) where \(W_i > B_j\) for the first time, the ball cannot cross that step, so it stops at cell \(i\).
• If \(W_i \le B_j\) for all steps, the ball crosses every step and reaches cell \(M\).

Therefore, the answer can be expressed as follows:

• If \(\min\{ i \mid W_i > B_j \}\) exists, the stopping cell is \(i\)
• If it does not exist, the stopping cell is \(M\)

A naive approach of checking steps from left to right for each ball results in \(O(N(M-1))\) in the worst case, which is clearly too slow given the constraints \(N, M \le 2\times 10^5\).

What we need is a mechanism to efficiently find “the first position where \(W_i > x\) in the array \(W\)” for a given weight \(x\).

Algorithm

We use a segment tree (range maximum) to find “the first position where \(W_i > x\)” in \(O(\log M)\).

1. Build the segment tree (range maximum)

• Place \(W_1, \dots, W_{M-1}\) at the leaves
• Each node stores the maximum value of its interval

This way, we can determine whether “a value exceeding \(x\) exists” in any interval by checking if the interval maximum is greater than \(x\).

2. Find “the first \(i\) such that \(W_i > x\)” (descend the tree)

The function first_gt(x) works as follows:

1. First, check the overall maximum seg[1]
   • If seg[1] <= x, there is no \(W_i > x\) anywhere → the answer is \(M\)
2. Otherwise, descend from the root
   • If the maximum of the left child interval is > x, the answer is in the left side, so go left
   • Otherwise, go right Repeating this until reaching a leaf gives us “the leftmost position where \(W_i > x\).”

The leaf position obtained is the step number \(i\) (1-indexed), so the cell number where the ball stops is directly \(i\) (because the ball cannot cross step \(i\) and remains at cell \(i\)).

Concrete Example

Let \(M=5,\; W=[3,1,4,2]\) (4 steps).

• When \(B=3\): \(W_1=3\) can be crossed (\(3\ge3\)) \(W_2=1\) can also be crossed \(W_3=4\) cannot be crossed (\(3<4\)) So the first \(W_i > 3\) is at \(i=3\), and the stopping cell is 3.

• When \(B=10\): Every step satisfies \(W_i \le 10\), so the ball reaches the end: 5.

Complexity

• Time complexity: Segment tree construction \(O(M)\), each ball query \(O(\log M)\), giving an overall complexity of \(O(M + N\log M)\)
• Space complexity: \(O(M)\) for the segment tree

Implementation Notes

• The length of \(W\) is \(M-1\), so the segment tree leaves correspond to that many elements (in the code, n = M-1).

• It is important that first_gt(x) returns \(M\) when no position is found (the case where all steps can be crossed).

• When descending the tree, the policy “if the left subtree contains a value \(>x\), go left; otherwise go right” guarantees that the leftmost position is always found.

• Rounding up the segment tree size to the next power of 2 simplifies the implementation (doubling size repeatedly).

  Source Code

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    M = next(it)

    n = M - 1
    W = [next(it) for _ in range(n)]
    B = [next(it) for _ in range(N)]

    size = 1
    while size < n:
        size <<= 1

    seg = [-1] * (2 * size)
    seg[size:size + n] = W
    for i in range(size - 1, 0, -1):
        seg[i] = seg[2 * i] if seg[2 * i] > seg[2 * i + 1] else seg[2 * i + 1]

    def first_gt(x):
        if seg[1] <= x:
            return M
        idx = 1
        l, r = 0, size
        while idx < size:
            mid = (l + r) >> 1
            left = idx << 1
            if seg[left] > x:
                idx = left
                r = mid
            else:
                idx = left | 1
                l = mid
        return l + 1  # 1-based index i where W_i > x, ball stops at square i

    out = []
    for x in B:
        out.append(str(first_gt(x)))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.