Overview

Given the initial stock quantities for each product and sequentially arriving shipping requests, the problem asks to process shipments only when sufficient stock is available, and to determine the number of successfully fulfilled requests.

Analysis

This problem is a straightforward simulation where we manage the stock quantity of each product while processing shipping requests in order. The key point is that a shipment succeeds only when the stock is greater than or equal to the requested quantity, in which case the stock decreases. Partial shipments are not allowed, and failed requests are not reprocessed. Given the constraints, since the number of products N and the number of requests M can be up to 200,000, efficient processing is necessary.

Algorithm

1. Store the initial stock quantities of each product in an array
2. Process each shipping request in order
3. For each request, check the current stock of the target product
4. If the stock quantity is greater than or equal to the requested quantity:
   • Decrease the stock by the requested quantity
   • Increment the success count by 1
5. If the stock quantity is less than the requested quantity:
   • Do nothing and move on to the next request
6. After processing all requests, output the success count

Complexity

• Time complexity: \(O(M)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Product numbers are given as 1-indexed, so convert to 0-indexed when accessing the array (f-1)

• Use a copy of the initial stock array for inventory management

• Use sys.stdin.read() for efficient input reading

• Each request only requires a simple comparison and subtraction, so processing is fast

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    if not data:
        print(0)
        return
        
    n = int(data[0])
    m = int(data[1])
    R = list(map(int, data[2:2+n]))
    requests = []
    index = 2 + n
    for i in range(m):
        f = int(data[index])
        s = int(data[index+1])
        index += 2
        requests.append((f, s))
    
    stock = R[:]
    success_count = 0
    
    for f, s in requests:
        idx = f - 1
        if stock[idx] >= s:
            stock[idx] -= s
            success_count += 1
            
    print(success_count)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.