Overview

This is a problem where you place \(N\) books one by one onto the leftmost available space that satisfies the weight capacity condition, and determine the total number of books successfully placed. We use a segment tree to efficiently find the “leftmost position satisfying the condition.”

Analysis

Issues with the Naive Approach

The most intuitive method is to scan spaces from left to right for each book, finding a space that is “not yet used & has sufficient weight capacity.” However, in the worst case this takes \(O(M)\) per book, resulting in \(O(N \times M)\) overall. Since \(N, M\) can be up to \(2 \times 10^5\), this yields approximately \(4 \times 10^{10}\) operations, which causes TLE.

Key Insight

The required operations are the following two:

1. Search: Among the available spaces, find the leftmost position where the weight capacity is at least \(R_i\)
2. Update: Mark the space where a book was placed as “used” (so it won’t be selected again)

Using a segment tree, both operations can be performed in \(O(\log M)\).

Algorithm

Segment Tree Solution

Each node of the segment tree stores the maximum weight capacity within its interval.

Search (find_leftmost_ge)

To find the leftmost space with weight capacity at least \(val\), we descend from the root as follows:

1. If the root node’s maximum value is less than \(val\), no space satisfies the condition → return \(-1\)
2. If the left child’s maximum value is at least \(val\), move to the left child (a qualifying position exists on the left side)
3. Otherwise, move to the right child
4. When a leaf node is reached, that position is the answer

This search traverses only the height of the tree, so it runs in \(O(\log M)\).

Update (update)

Overwrite the weight capacity of the space where a book was placed to \(0\) (since \(R_i \geq 1\), setting it to \(0\) ensures it will never be selected again). Recompute the maximum values from the leaf up to the root, completing in \(O(\log M)\).

Overall Flow

1. Build the segment tree from the weight capacity array \(C\)
2. Process books \(1, 2, \ldots, N\) in order
   • Search the segment tree for the leftmost position with capacity at least \(R_i\)
   • If found, update that space’s value to \(0\) and increment the count by \(+1\)
   • If not found, skip
3. Output the count

Concrete Example

When \(M = 5\) and the space weight capacities are \(C = [3, 1, 4, 1, 5]\), the root of the segment tree holds the maximum value \(5\).

• Book with weight \(2\) → searching from the left, \(C_1 = 3 \geq 2\) → place on space 1, update \(C_1\) to \(0\)
• Book with weight \(4\) → \(C_1=0, C_2=1, C_3=4 \geq 4\) → place on space 3, update \(C_3\) to \(0\)
• Book with weight \(5\) → \(C_5 = 5 \geq 5\) → place on space 5

Complexity

• Time complexity: \(O((N + M) \log M)\) — \(O(M)\) for building the segment tree, \(O(\log M)\) for processing each book
• Space complexity: \(O(M)\) — array size of the segment tree

Implementation Notes

• The segment tree size should be the smallest power of 2 that is at least \(M\). Excess leaves are filled with \(0\), so they naturally fail the weight capacity condition \(R_i \geq 1\) and are automatically ignored.

• By updating the weight capacity of a used space to \(0\), it is automatically skipped in subsequent searches.

• In Python, input is read all at once using stdin.buffer.read() to speed up input processing.

  Source Code

import sys
from sys import stdin

def main():
    input_data = stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    R = [int(input_data[idx + i]) for i in range(N)]; idx += N
    C = [int(input_data[idx + i]) for i in range(M)]; idx += M

    # Segment tree with max, supporting:
    # - query: find leftmost position where C[pos] >= value
    # - update: set position to -infinity (mark as used)
    
    size = 1
    while size < M:
        size *= 2
    
    tree = [0] * (2 * size)
    
    # Build
    for i in range(M):
        tree[size + i] = C[i]
    for i in range(M, size):
        tree[size + i] = 0
    for i in range(size - 1, 0, -1):
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
    
    def find_leftmost_ge(val):
        # Find leftmost index where C[index] >= val
        if tree[1] < val:
            return -1
        node = 1
        while node < size:
            if tree[2 * node] >= val:
                node = 2 * node
            else:
                node = 2 * node + 1
        return node - size
    
    def update(pos, val):
        pos += size
        tree[pos] = val
        pos >>= 1
        while pos >= 1:
            tree[pos] = max(tree[2 * pos], tree[2 * pos + 1])
            pos >>= 1
    
    count = 0
    for i in range(N):
        pos = find_leftmost_ge(R[i])
        if pos != -1:
            count += 1
            update(pos, 0)
    
    print(count)

main()

---

This editorial was generated by claude4.6opus-thinking.