Overview

This problem asks us to determine where each ball stops when rolling on stair-shaped cells. It can be solved efficiently using binary search.

Analysis

Understanding the Problem

A ball starts from cell 1 and continues rolling to the next cell as long as its weight \(B_j\) is greater than or equal to the step threshold \(W_i\).

Naive Approach and Its Issues

If we simulate each ball starting from cell 1, we need up to \(O(M)\) checks per ball. With \(N\) balls, the total complexity is \(O(NM)\). When \(N, M\) are at most \(2 \times 10^5\), this results in up to \(4 \times 10^{10}\) operations, causing TLE.

Key Insight

For a ball to reach cell \(k\), it must cross all intermediate steps. In other words, to advance from cell 1 to cell \(k\): $\(B_j \geq W_1 \text{ and } B_j \geq W_2 \text{ and } \cdots \text{ and } B_j \geq W_{k-1}\)$

This is equivalent to: $\(B_j \geq \max(W_1, W_2, \ldots, W_{k-1})\)$

Using Cumulative Maximum

If we define \(\text{max\_W}[i] = \max(W_1, W_2, \ldots, W_{i+1})\), this array is monotonically non-decreasing (since the maximum can never decrease).

Example: When \(W = [3, 1, 4, 2]\), \(\text{max\_W} = [3, 3, 4, 4]\)

For monotonically non-decreasing arrays, we can use binary search!

Algorithm

1. Preprocessing: Compute the cumulative maximum array \(\text{max\_W}\)

   • \(\text{max\_W}[0] = W[0]\)
   • \(\text{max\_W}[i] = \max(\text{max\_W}[i-1], W[i])\) (for \(i \geq 1\))

2. Binary search for each ball:

   • For a ball with weight \(b\), find the maximum \(i\) such that \(\text{max\_W}[i] \leq b\)
   • bisect_right(max_W, b) returns “the first position where a value greater than \(b\) appears”
   • Therefore, bisect_right(max_W, b) steps can be crossed
   • The stopping cell is bisect_right(max_W, b) + 1

Concrete Example

For \(M = 5\), \(W = [3, 1, 4, 2]\), ball weight \(b = 3\): - \(\text{max\_W} = [3, 3, 4, 4]\) - bisect_right([3, 3, 4, 4], 3) = 2 (values at indices 0, 1 are at most 3) - 2 steps can be crossed, so the ball stops at cell \(2 + 1 = 3\)

Complexity

• Time complexity: \(O(M + N \log M)\)
  • Computing cumulative maximum: \(O(M)\)
  • Binary search for each ball: \(O(\log M)\) × \(N\) balls = \(O(N \log M)\)
• Space complexity: \(O(M + N)\)
  • Cumulative maximum array: \(O(M)\)
  • Storing results: \(O(N)\)

Implementation Notes

• bisect_right returns the “insertion position”, which can be directly used as “the number of steps that can be crossed”

• The cumulative maximum array is managed with 0-indexing, where \(\text{max\_W}[i]\) represents the maximum from \(W[0]\) to \(W[i]\)

• Since there are \(N\) lines of output, using '\n'.join() to output all at once is faster than printing line by line

  Source Code

import bisect

def main():
    import sys
    input = sys.stdin.readline
    
    N, M = map(int, input().split())
    W = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    # Compute max_W[i] = max(W[0], W[1], ..., W[i])
    # This represents the minimum weight needed to advance from cell 1 to cell i+2
    max_W = [0] * (M - 1)
    max_W[0] = W[0]
    for i in range(1, M - 1):
        max_W[i] = max(max_W[i - 1], W[i])
    
    # max_W is monotonically non-decreasing
    # When a ball has weight b, find the maximum i such that b >= max_W[i]
    # That ball can advance to cell i+2 (crossing i+1 steps)
    
    results = []
    for b in B:
        # Use binary search to find the maximum i such that b >= max_W[i]
        # i.e., the maximum i where max_W[i] <= b
        # Use bisect_right to find the first position greater than b, and we can advance up to just before that
        idx = bisect.bisect_right(max_W, b)
        # Can cross idx steps -> reaches cell idx+1
        results.append(idx + 1)
    
    print('\n'.join(map(str, results)))

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.