Overview

This is a problem where you place \(N\) books one by one into the “leftmost available” empty space on a bookshelf with \(M\) spaces that satisfies the weight condition, and determine how many books can be placed in total.

Analysis

Consider a naive approach where, for each book, we search for a qualifying space from left to right (linear search). In this case, for each book we may need to check up to \(M\) spaces, so the worst-case time complexity is \(O(N \times M)\). Given the constraints \(N, M \leq 2 \times 10^5\), this could require up to about \(4 \times 10^{10}\) operations, which would exceed the time limit (TLE).

To solve this efficiently, we need to perform the following two operations quickly: 1. Find the empty space with the smallest index whose weight capacity is at least \(R_i\). 2. Mark the space where a book is placed as “used.”

To achieve this, we use a data structure called a Segment Tree.

Algorithm

Each node of the segment tree stores the “maximum weight capacity” among the empty spaces in its interval.

1. Building the Segment Tree

Place the weight capacities \(C_1, C_2, \ldots, C_M\) of each shelf space at the leaves (bottom layer), and let each parent node hold the maximum of its left and right children. This allows us to reference the maximum weight capacity within any interval in \(O(1)\).

2. Searching for a Qualifying Space

When searching for a place to put a book of weight \(R_i\), we traverse from the root (entire range) as follows (\(O(\log M)\)): - If the current node’s maximum value is less than \(R_i\), there is no valid space in this interval. - If the left child’s maximum value is at least \(R_i\), a qualifying space exists in the left interval, so we go left. - If the left child’s maximum value is less than \(R_i\) and the right child’s maximum value is at least \(R_i\), we go right.

By repeating this until we reach a leaf, we can quickly find the “leftmost space that satisfies the condition.”

3. Updating the Space

Rewrite the weight capacity of the space where the book was placed to \(0\). Then, recalculate the maximum values from that leaf back up to the root to update the tree (\(O(\log M)\)).

4. Overall Flow

Repeat the above search and update for all books \(R_1, R_2, \ldots, R_N\). Count the number of times a book was successfully placed, and output this as the final answer.

Complexity

• Time complexity: \(O((N + M) \log M)\)
  • Building the segment tree takes \(O(M)\).
  • Search and update for each book takes \(O(\log M)\). Since there are \(N\) books, this totals \(O(N \log M)\).
• Space complexity: \(O(M)\)
  • The array for managing the segment tree uses \(O(M)\) memory.

Implementation Tips

• Segment tree size: Using the smallest power of two (\(2^k\)) that is at least \(M\) as the number of leaves simplifies the implementation.

• Fast I/O: In Python, since the amount of data is large (over \(4 \times 10^5\) integers), reading all input at once using sys.stdin.read().split() can reduce execution time.

• Update optimization: When updating parent node values, stopping the update early if the value hasn’t changed can provide constant-factor speedup.

  Source Code

import sys

# 本棚への配架問題を解決するために、セグメント木（Segment Tree）を使用します。
# セグメント木は、各区間における耐荷重の最大値を保持します。
# これにより、ある重さ以上の耐荷重を持つ「最も左側（番号が小さい）の空きスペース」を効率的に探索できます。

def solve():
    # 標準入力からすべてのデータを一括で読み込み、高速化を図ります。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not input_data:
        return
    
    # N: 本の冊数, M: 本棚のスペース数
    N = int(input_data[0])
    M = int(input_data[1])
    
    # R: 各本の重さ, C: 各スペースの耐荷重
    R = list(map(int, input_data[2:2+N]))
    C = list(map(int, input_data[2+N:2+N+M]))
    
    # セグメント木のサイズを決定します（M以上の最小の2のべき乗）。
    size = 1
    while size < M:
        size <<= 1
    
    # tree[1]をルートとし、tree[size]以降を葉とする配列を初期化します。
    # 各要素は、その範囲内にある空きスペースの耐荷重の最大値を表します。
    tree = [0] * (2 * size)
    for i in range(M):
        tree[size + i] = C[i]
    
    # ボトムアップでセグメント木を構築します。
    for i in range(size - 1, 0, -1):
        left_val = tree[i << 1]
        right_val = tree[(i << 1) | 1]
        if left_val > right_val:
            tree[i] = left_val
        else:
            tree[i] = right_val
            
    placed_books_count = 0
    
    # 各本について順番に配架場所を検討します。
    for r in R:
        # 本棚全体の最大耐荷重が本の重さ未満であれば、その本は置けません。
        if tree[1] < r:
            continue
        
        # 条件を満たす最も左側のスペースを木の上から探索します。
        idx = 1
        while idx < size:
            left_child = idx << 1
            # 左側の子（より小さい番号のスペースを含む範囲）に条件を満たすスペースがあるか確認
            if tree[left_child] >= r:
                idx = left_child
            else:
                # 左側にない場合は右側の子へ
                idx = left_child | 1
        
        # 本を置くことができたのでカウントを増やします。
        placed_books_count += 1
        
        # 本を置いたスペースの耐荷重を0に更新（既に使用済みであることを示す）。
        tree[idx] = 0
        
        # 木を葉からルートに向かって更新します。
        idx >>= 1
        while idx >= 1:
            left_val = tree[idx << 1]
            right_val = tree[(idx << 1) | 1]
            
            if left_val > right_val:
                new_max = left_val
            else:
                new_max = right_val
            
            # 最大値が変化しなくなったら、それ以上の親の更新は不要です。
            if tree[idx] == new_max:
                break
            tree[idx] = new_max
            idx >>= 1
                
    # 最終的に本棚に置くことができた本の冊数を出力します。
    sys.stdout.write(str(placed_books_count) + '\n')

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.