Overview

Given the initial stock of products, \(M\) shipping requests arrive in order. We simulate the process where shipping is performed only when there is sufficient stock, and count the number of successful shipments.

Analysis

This problem can be solved by simulating the shipping process in order, exactly as described in the problem statement.

The key point in performing the simulation is how quickly we can check and update “the current stock of product \(F_j\).” If for each request we “look through products \(1\) to \(N\) in order to find the one whose product number matches \(F_j\),” then each request requires up to \(N\) checks, resulting in \(O(NM)\) total time. Since the constraints are \(N, M \leq 2 \times 10^5\), this would exceed the time limit (TLE).

To solve this, it is important to manage product stock using an array (list) and treat the product number as the array index. Accessing data by specifying an array index takes \(O(1)\) (constant time), making it possible to process all requests efficiently.

Algorithm

1. Store the initial stock of each product in an array R of length \(N\).
2. Prepare a variable ans to count the number of successful shipments, initialized to 0.
3. Process the \(M\) shipping requests in order. For each request, perform the following:
   • Check the stock R[F_j] corresponding to the requested product number \(F_j\).
   • If R[F_j] is at least the requested quantity \(S_j\) (R[F_j] >= S_j), the shipment is successful. Subtract \(S_j\) from R[F_j] and add \(1\) to ans.
   • If R[F_j] is less than \(S_j\), the shipment fails and nothing is done.
4. Output the value of ans after all requests have been processed.

Complexity

• Time complexity: \(O(N + M)\) Creating the initial stock array takes \(O(N)\). Each request is processed in \(O(1)\) via index access, and this is repeated \(M\) times for \(O(M)\). The total is \(O(N + M)\), which runs sufficiently fast under the given constraints.
• Space complexity: \(O(N + M)\) The array for managing stock uses \(O(N)\) space. In the solution code, since all input is read at once, the total space usage including the stored input data is \(O(N + M)\).

Implementation Notes

• Conversion between 0-indexed and 1-indexed In the problem statement, product numbers range from \(1\) to \(N\) (1-indexed), but arrays in many programming languages including Python start from \(0\) (0-indexed). Therefore, by subtracting \(1\) from the input product number \(F\) to get F - 1, we can access the correct position in the array.

• Fast I/O Since the number of input data items can be up to approximately \(6 \times 10^5\) (\(N + 2M + 2\) items), using fast I/O methods such as sys.stdin.read().split() instead of calling input() multiple times can significantly reduce execution time.

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    R = [int(x) for x in input_data[2:2+N]]
    
    ans = 0
    idx = 2 + N
    for _ in range(M):
        F = int(input_data[idx]) - 1
        S = int(input_data[idx+1])
        idx += 2
        
        if R[F] >= S:
            R[F] -= S
            ans += 1
            
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.