概要

各ボールは「越えられない段差（必要重さが自分より大きい段差）」に初めて遭遇したマスで止まるので、各 \(B_j\) について「最初に \(W_i > B_j\) となる \(i\)」を高速に求める問題です。

考察

ボールがマス \(p\) から \(p+1\) へ進める条件は \(B_j \ge W_p\) です。
つまり、

• \(W_1, W_2, \dots\) を左から見ていき、
• 初めて \(W_i > B_j\) となる段差 \(i\) があれば、ボールはその段差を越えられないので マス \(i\) で停止します。
• もし最後まで \(W_i \le B_j\) なら、すべての段差を越えられるので マス \(M\) まで到達します。

したがって、答えは次の形で書けます：

• \(\min\{ i \mid W_i > B_j \}\) が存在するなら停止マスは \(i\)
• 存在しないなら停止マスは \(M\)

素朴に各ボールごとに左から順に段差を確認すると、最悪で \(O(N(M-1))\) となり、制約 \(N,M \le 2\times 10^5\) では確実に間に合いません。

必要なのは「ある重さ \(x\) に対して、配列 \(W\) の中で最初に \(W_i > x\) となる位置」を高速に探す仕組みです。

アルゴリズム

セグメント木（区間最大値）を使って「最初に \(W_i > x\) となる位置」を \(O(\log M)\) で求めます。

1. セグメント木を作る（区間最大値）

• 葉に \(W_1,\dots,W_{M-1}\) を置く
• 各ノードにはその区間の最大値を持たせる

こうすると、任意の区間に「\(x\) を超える値が存在するか」は、区間最大値が \(x\) より大きいかどうかで判定できます。

2. 「最初に \(W_i > x\) となる \(i\)」を探す（木を降りる）

関数 first_gt(x) の動きは次の通りです：

1. まず全体の最大値 seg[1] を見る
   
   • seg[1] <= x なら、どこにも \(W_i > x\) はない → 答えは \(M\)
2. そうでなければ、根から降りる
   
   • 左の子区間の最大値が > x なら、答えは左側にあるので左へ
   • そうでなければ右へ
     これを葉まで繰り返すと、「最初に \(W_i > x\) となる最左位置」が得られます。

得られた葉の位置が段差番号 \(i\)（1-indexed）なので、ボールが止まるマス番号もそのまま \(i\) になります（段差 \(i\) を越えられず、マス \(i\) にいるため）。

具体例

\(M=5,\; W=[3,1,4,2]\)（段差は4本）とします。

• \(B=3\) のとき：
  \(W_1=3\) は越えられる（\(3\ge3\)）
  \(W_2=1\) も越えられる
  \(W_3=4\) は越えられない（\(3<4\)）
  よって最初に \(W_i > 3\) となるのは \(i=3\)、停止マスは 3。

• \(B=10\) のとき：どの段差も \(W_i \le 10\) なので最後まで進めて 5。

計算量

• 時間計算量: セグメント木構築 \(O(M)\)、各ボールの検索 \(O(\log M)\) より全体で \(O(M + N\log M)\)
• 空間計算量: セグメント木に \(O(M)\)

実装のポイント

• \(W\) の長さは \(M-1\) 本なので、セグ木の葉もその分だけ持つ（コード中では n = M-1）。

• first_gt(x) で「見つからない場合は \(M\)」を返すのが重要です（全部越えられるケース）。

• 木を降りるときは「左部分木に \(>x\) があるなら左、なければ右」という方針にすると、最左の位置が必ず得られます。

• セグ木のサイズは 2 冪に切り上げて管理すると実装が簡単です（size を倍々に増やす）。

  ソースコード

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()

---

この解説は gpt-5.2-high によって生成されました。