Overview

In a warehouse with limited stock, shipping requests arrive in order. If there is sufficient stock for a request, the shipment is made; otherwise, the request is skipped. The problem asks how many shipments were successfully completed.

Analysis

It is immediately clear that this problem can be solved with a straightforward simulation. That is, for each shipping request, we check “Is the current stock of the specified product at least the requested quantity?” If the condition is met, we reduce the stock and increment the success count, processing requests in order.

However, there are several key points to note:

• Index handling: In the input, product numbers are given as \(1\)-indexed (starting from 1), but array indices are typically \(0\)-indexed (starting from 0), so conversion is necessary.
• Efficient input processing: In Python, reading standard input line by line can be slow. Especially when constraints are large (\(N, M \sim 2 \times 10^5\)), reading all input at once using sys.stdin.read or input().split() is faster.
• Partial shipments are not allowed: If stock is insufficient, no shipment is made at all and we move on to the next request, so stock management must be handled precisely.

Taking these points into account, the effective approach is to manage stock using a list and process each request sequentially from the beginning.

Algorithm

1. Read all input at once and store the initial stock quantities of products in a list stock.
2. Process each shipping request in order:
   • Convert the product number \(F_j\) (1-indexed) specified in the request to 0-indexed.
   • Check whether the current stock stock[F_j] of that product is at least the requested quantity \(S_j\).
   • If there is sufficient stock, reduce the stock and increment the success count.
3. Output the final success count.

With this method, each request can be processed in constant time, so the overall solution runs sufficiently fast.

Complexity

• Time complexity: \(O(N + M)\) (Reading input takes \(O(N + M)\), and processing each request takes \(O(1)\), so the total is linear)
• Space complexity: \(O(N + M)\) (Memory required to store stock information and input data)

Implementation Notes

• Since product numbers in the input are 1-indexed, always convert to 0-indexed (subtract 1) when handling them internally.

• To process large amounts of input efficiently, use sys.stdin.read or input().split().

• Stock updates are simple subtractions, so as long as the conditional branching is correct, bugs are unlikely.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    # 在庫リスト
    R = list(map(int, data[2:2+N]))
    
    # 在庫を管理するためのリスト（0-indexed）
    stock = R[:]
    
    success_count = 0
    
    # 出荷依頼を順に処理
    idx = 2 + N
    for _ in range(M):
        F = int(data[idx]) - 1  # 0-indexedにするために-1
        S = int(data[idx+1])
        idx += 2
        
        if stock[F] >= S:
            stock[F] -= S
            success_count += 1
    
    print(success_count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.