Overview

We simulate the operation of placing each book at “the leftmost available space with sufficient weight capacity,” and determine the total number of books that can be placed.

Analysis

To place book \(i\) (with weight \(R_i\)), we need to find “the smallest \(j\) such that \(C_j \ge R_i\)” among the unused spaces.

• Naive approach
  If we scan available spaces from left to right for each book, the worst case is:

  • \(N=2\times 10^5\) books
  • \(M=2\times 10^5\) spaces
    resulting in \(O(NM)\), which is far too slow.

• Key observation
  “Does a qualifying available space exist in a given interval?” can be determined by looking at the maximum weight capacity in that interval.
  For example, if the maximum value in interval \([l,r]\) is \(< R_i\), then no valid placement exists in that interval.
  Conversely, if the maximum is \(\ge R_i\), then there is guaranteed to be a valid placement somewhere in that interval.

By using a segment tree as a data structure to efficiently handle “interval maximum queries,” we can: - Determine “whether a valid placement exists” in \(O(1)\) (by checking the root value) - Find “the leftmost valid placement” in \(O(\log M)\) - “Mark that space as used” with an update in \(O(\log M)\)

Algorithm

We manage the array \(C\) (weight capacity of each space) with a segment tree.

• Each node of the segment tree stores the maximum value of its interval
• When a space is used, set the corresponding leaf’s value to 0 (since \(R_i \ge 1\), this sufficiently represents “can never be used again”)

For each book (with weight \(x=R_i\)), we do the following:

1. Check if placement is possible at all
   The root seg[1] of the segment tree holds the overall maximum.
   
   • If seg[1] < x, the book cannot be placed anywhere, so skip it.
2. Descend the tree to find the leftmost valid position (binary search-like descent)
   Starting from the root, descend to a leaf using the following rule:
   • If the left child’s maximum is \(\ge x\), the answer is on the left side, so go left
   • Otherwise, go right (a valid position must exist on the right side)

This yields the “smallest index satisfying the condition (leftmost).” 3. Update that position as used
Set the found leaf to 0, then recompute and update the maximum values going back up to the root. 4. Increment the count of successfully placed books.

Concrete Example

When \(C=[3,1,4,2]\) and the book weight is \(x=2\): - The overall maximum is 4, so placement is possible - “The maximum of the left half [3,1] is 3,” so go left → further, [3] is 3 which is sufficient → the leftmost position is position 1
In this way, by checking “whether the maximum is sufficient” to decide whether to go left, we can efficiently identify the leftmost position.

Complexity

• Time complexity: \(O((N+M)\log M)\)
  (Construction is \(O(M)\), and for each book, search and update take \(O(\log M)\))
• Space complexity: \(O(M)\)
  (Segment tree array)

Implementation Notes

• For ease of handling, the segment tree rounds the number of leaves up to size, the smallest power of \(2\) that is \(\ge M\).

• The descent to find “the leftmost position” is implemented by the rule: if seg[left_child] >= x, go left; otherwise, go right. (It is crucial here that seg[1] >= x is guaranteed at the root.)

• Used spaces are marked by setting their value to 0. Since \(R_i \ge 1\) by the constraints, 0 means “no book can ever be placed here,” ensuring correct behavior.

  Source Code

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

---

This editorial was generated by gpt-5.2-high.