Overview

This is a simulation problem where you manage the inventory of \(N\) types of books and process \(M\) lending requests in chronological order. For each request, you determine whether there is sufficient inventory, and only reduce the inventory if there is enough.

Analysis

The key points of this problem are accurately implementing the conditions: “process requests in order” and “do nothing if inventory is insufficient”.

1. Running the Simulation: It is efficient to manage the current inventory count of each book using an array (a list in Python). By storing the inventory of book with ID \(i\) in A[i-1] (when 0-indexed), you can reference and update the inventory in \(O(1)\) for each request.
2. Checking the Constraints: Since \(N\) and \(M\) are at most \(10^5\), processing all requests sequentially results in approximately \(10^5\) operations. This is well within the computation limit that typical programming languages can handle in 1 second (approximately \(10^8\) operations).
3. Fast Input/Output: Since the number of inputs is large, calling input() repeatedly in Python may result in exceeding the time limit (TLE). It is effective to read all input at once using techniques such as sys.stdin.read().split().

Algorithm

1. Store the initial inventory counts \(A_1, A_2, \dots, A_N\) in an array A.
2. Read the \(M\) lending requests \((B_j, C_j)\) one by one in order.
3. Check the current inventory A[B_j - 1] corresponding to book ID \(B_j\).
   • If A[B_j - 1] >= C_j, reduce the inventory by \(C_j\) (A[B_j - 1] -= C_j).
   • Otherwise, skip that request.
4. After processing all requests, output the contents of array A in order.

Complexity

• Time Complexity: \(O(N + M)\)
  • Reading the initial inventory takes \(O(N)\), and processing the requests takes \(O(M)\).
• Space Complexity: \(O(N)\)
  • An array is needed to store the inventory counts for \(N\) types of books.

Implementation Notes

• Converting to 0-indexed: In the problem statement, book IDs are given from \(1\) to \(N\), but since arrays in programs typically start from \(0\), you need to adjust the index by using B_j - 1.

• Optimization in Python: By using sys.stdin.read().split(), you can retrieve a large number of values as a list all at once, significantly reducing the reading time. Additionally, when outputting, writing *A allows you to concisely unpack and print the list elements separated by spaces.

  Source Code

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにする
    # sys.stdin.read().split() は大量の入力を高速に読み込む際に有効です
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は終了
    if not input_data:
        return
    
    # 本の種類数 N と貸出申請の件数 M を取得
    N = int(input_data[0])
    M = int(input_data[1])
    
    # 各本の初期蔵書数 A_1, ..., A_N を取得
    # 管理番号 i の本は 0-indexed で A[i-1] に対応させる
    A = list(map(int, input_data[2:N+2]))
    
    # 貸出申請の処理
    # 貸出申請の情報は input_data[N+2] 以降に B_j, C_j のペアで格納されている
    ptr = N + 2
    for _ in range(M):
        # 管理番号 B_j と貸出希望冊数 C_j
        b_j = int(input_data[ptr])
        c_j = int(input_data[ptr+1])
        ptr += 2
        
        # 0-indexed に変換した管理番号
        idx = b_j - 1
        
        # 蔵書数が申請された冊数以上の場合は貸し出しを実行
        if A[idx] >= c_j:
            A[idx] -= c_j
            
    # すべての申請を処理した後の蔵書数を管理番号 1 から N の順にスペース区切りで出力
    # print(*A) はリストの要素をスペース区切りで展開して出力する
    print(*(A))

if __name__ == '__main__':
    solve()

This editorial was generated by gemini-3-flash-thinking.