概要

各本の在庫 \(A_i\) を持ちながら、貸出申請 \((B_j, C_j)\) を順番に処理し、在庫が足りるときだけ減らした最終在庫を求める問題です。

考察

重要なのは「申請は順番に処理し、在庫が足りない申請はスキップして在庫は変わらない」という点です。
つまり、各申請は「その時点の在庫」を見て可否が決まるため、後の申請にも影響します。

ここでやることは非常に素直で、各申請について

• 本 \(B_j\) の現在庫が \(C_j\) 以上なら \(A_{B_j} \leftarrow A_{B_j} - C_j\)
• そうでなければ何もしない

を繰り返すだけです。

制約は \(N, M \le 10^5\) なので、申請を1件ずつ処理する \(O(M)\) のシミュレーションで十分間に合います。
一方で、例えば「毎回全ての本を探す」「不要に複雑なデータ構造で更新する」など、1申請あたり \(O(N)\) かかる実装にすると \(O(NM)\) となり、最大で \(10^{10}\) 規模になってTLEします。

（具体例）
在庫 \(A=[3,1]\)、申請が 1. \((1,2)\) → 在庫3あるので実行、\(A=[1,1]\) 2. \((1,2)\) → 在庫1しかないのでスキップ、\(A=[1,1]\) 3. \((2,1)\) → 実行、\(A=[1,0]\) のように、順番通りに「足りるか判定→引く」を繰り返せばよいです。

アルゴリズム

1. 配列 \(A\) を読み込む（0-indexで管理すると楽）。
2. 各申請 \((B, C)\) を入力順に処理する。
   • \(b = B - 1\) として 0-index に直す
   • もし \(A[b] \ge C\) なら \(A[b] \mathrel{-}= C\)（在庫を減らす）
   • そうでなければ何もしない
3. 最後に配列 \(A\) を出力する。

計算量

• 時間計算量: \(O(N + M)\)（初期在庫の読み込み \(O(N)\) と申請処理 \(O(M)\)）
• 空間計算量: \(O(N)\)（在庫配列 \(A\) のみ）

実装のポイント

• 入力が最大 \(2\times 10^5\) 行相当になるので、Pythonでは sys.stdin.buffer.read() のような高速入力を使うと安全です。

• 本の番号 \(B_j\) は \(1\) 始まりなので、配列アクセス用に -1 して 0-index に直します。

• 出力は " ".join(...) でまとめて1行にすると高速です。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)
    N = int(next(it))
    M = int(next(it))
    A = [int(next(it)) for _ in range(N)]
    for _ in range(M):
        b = int(next(it)) - 1
        c = int(next(it))
        if A[b] >= c:
            A[b] -= c
    sys.stdout.write(" ".join(map(str, A)))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。