Overview

This is a problem where you manage the stock quantity of each product, process shipping requests in order, and count the “number of requests that had sufficient stock.”

Analysis

The key point is that each request’s success or failure is determined solely by the stock at that moment, and stock decreases only when a request succeeds. A failed request does not reduce stock, and there are no retries later.

From this rule, what we need to do is straightforward:

• When request \((F_j, S_j)\) arrives, check stock \(R_{F_j}\):
  • If \(R_{F_j} \ge S_j\), it succeeds: \(R_{F_j} \leftarrow R_{F_j} - S_j\)
  • Otherwise, it fails: do nothing
• Count the number of successes

That’s all.

We need to “look up the stock each time,” but since product numbers are given directly, if we store stock in an array, we can process each request in \(O(1)\). Conversely, if we search for stock using another method each time (e.g., searching for a product in a list), it could be \(O(NM)\) in the worst case, which won’t be fast enough for \(N, M \le 2 \times 10^5\).

Also, since the input size is large, fast input methods are effective in Python, such as reading all at once with sys.stdin.buffer.read().

Concrete example: - Stock \(R = [5, 2]\) - Request: (3 units of product 1) → \(5 \ge 3\) success, stock becomes \([2,2]\) - Request: (4 units of product 1) → \(2 < 4\) failure, stock remains \([2,2]\) - Request: (2 units of product 2) → \(2 \ge 2\) success, stock becomes \([2,0]\) The number of successes is 2.

Algorithm

1. Store the stock quantity of each product in array R (using 0-indexing).
2. Process requests from the beginning in order:
   • Let f be the product number (0-indexed) and s be the shipping quantity.
   • If R[f] >= s, then set R[f] -= s and increment the success count ans by 1.
   • Otherwise, do nothing.
3. Output ans at the end.

Complexity

• Time complexity: \(O(N + M)\) (reading stock \(N\) times + processing \(M\) requests, each operation takes constant time)
• Space complexity: \(O(N)\) (stock array)

Implementation Notes

• Since the input size can be very large, it is safe to read input quickly using something like sys.stdin.buffer.read().split().

• Product numbers \(F_j\) are 1-indexed, so subtract -1 to convert to 0-indexed for array access.

• Stock quantities and request amounts can be up to \(10^9\), but since we only perform subtraction and comparison, Python’s int handles this without any issues.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    M = next(it)
    R = [next(it) for _ in range(N)]
    ans = 0
    for _ in range(M):
        f = next(it) - 1
        s = next(it)
        if R[f] >= s:
            R[f] -= s
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.