概要

各本を「まだ空いているスペースのうち、耐荷重が足りる最も左の場所」に置いていく操作をシミュレーションし、最終的に置けた本の冊数を求めます。

考察

本 \(i\)（重さ \(R_i\)）を置くには、未使用のスペースの中から「\(C_j \ge R_i\) を満たす最小の \(j\)」を探す必要があります。

• 素朴な方法
  各本ごとに左から順に空きスペースを探すと、最悪で

  • 本が \(N=2\times 10^5\) 冊
  • スペースが \(M=2\times 10^5\) 個
    なので、\(O(NM)\) となり到底間に合いません。

• 重要な観察
  「ある区間に条件を満たす空きスペースが存在するか？」は、区間の 最大耐荷重 を見れば分かります。
  例えば区間 \([l,r]\) の最大値が \(< R_i\) なら、その区間には置ける場所が存在しません。
  逆に最大値が \(\ge R_i\) なら、その区間内のどこかには必ず置ける場所があります。

この「区間の最大値」を高速に扱えるデータ構造として セグメント木 を使うことで、 - 「置ける場所が存在するか」を \(O(1)\)（根の値）で判定 - 「最も左の置ける場所」を \(O(\log M)\) で特定 - 「その場所を使用済みにする」更新を \(O(\log M)\)
で行えます。

アルゴリズム

セグメント木で配列 \(C\)（各スペースの耐荷重）を管理します。

• セグメント木の各ノードには、その区間の 最大値 を持たせる
• スペースを使ったら、その葉の値を 0 にする（\(R_i \ge 1\) なので「二度と使えない」表現として十分）

各本（重さ \(x=R_i\)）について次を行います：

1. 全体で置けるか判定
   セグメント木の根 seg[1] は全体の最大値。
   
   • seg[1] < x なら、どこにも置けないのでスキップ。
2. 最も左の置ける位置を二分探索的に降りて探す（木を降下）
   根から開始し、次の規則で葉まで降ります：
   • 左の子の最大値が \(\ge x\) なら、答えは左側にあるので左へ
   • そうでなければ右へ（右側には必ず存在するはず）

これで「条件を満たす最小のインデックス（最左）」が得られます。 3. その位置を使用済みに更新
見つけた葉を 0 にし、親へ向かって最大値を再計算して更新します。 4. 置けた本の数をカウントします。

具体例

\(C=[3,1,4,2]\)、本の重さが \(x=2\) のとき： - 全体最大は 4 なので置ける - 「左半分 [3,1] の最大は 3」なので左へ → さらに [3] は 3 で置ける → 最左は位置1
このように「最大値が足りるか」で左へ進むかを決めるため、最左の位置を高速に特定できます。

計算量

• 時間計算量: \(O((N+M)\log M)\)
  （構築が \(O(M)\)、各本ごとに探索・更新が \(O(\log M)\)）
• 空間計算量: \(O(M)\)
  （セグメント木配列）

実装のポイント

• セグメント木は扱いやすいように、葉の数を \(M\) 以上の最小の \(2\) の冪 size に揃えています。

• 「最も左の位置」を探す降下は、seg[left_child] >= x なら左、そうでなければ右、という判定で実現できます（このとき根で seg[1] >= x が保証されているのが重要）。

• 使用済みは値を 0 にしています。制約より \(R_i \ge 1\) なので、0 は「以後どの本も置けない」ことを意味し、正しく動作します。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)
    R = [next(it) for _ in range(N)]
    C = [next(it) for _ in range(M)]

    size = 1
    while size < M:
        size <<= 1
    seg = [0] * (2 * size)
    seg[size:size + M] = C
    for i in range(size - 1, 0, -1):
        seg[i] = seg[i << 1] if seg[i << 1] >= seg[i << 1 | 1] else seg[i << 1 | 1]

    ans = 0
    for x in R:
        if seg[1] < x:
            continue
        v = 1
        while v < size:
            lc = v << 1
            if seg[lc] >= x:
                v = lc
            else:
                v = lc | 1
        pos = v - size
        if pos >= M:
            continue
        seg[v] = 0
        v >>= 1
        while v:
            left = seg[v << 1]
            right = seg[v << 1 | 1]
            seg[v] = left if left >= right else right
            v >>= 1
        ans += 1

    print(ans)

if __name__ == "__main__":
    main()

---

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