概要

各図書館・各ジャンルの在庫数を配列で管理し、貸出申請を時系列に1件ずつ処理して在庫を減らす（0なら失敗回数を増やす）問題です。

考察

重要なのは、各申請が参照するのは「特定の図書館 \(v_k\) の特定ジャンル \(d_k\)」の在庫だけであり、他のジャンルや他の図書館の情報は不要という点です。
つまり、毎回やるべきことは次の2択だけです。

• その在庫が \(>0\) なら \(-1\)
• \(=0\) なら失敗回数 \(+1\)

ここで素朴にやりがちな失敗として、例えば以下のようなことがあります。

• 申請のたびに図書館の情報を入力から探し直す / 辞書検索を多用する
  
• 文字列として読み込んで毎回パースする
  
• 出力のたびに都度 print を大量に呼ぶ
  

本問題は最大で \(\sum M_i \le 10^5\)、申請数が \(Q \le 2\times 10^5\) と大きいため、「1申請あたり \(O(1)\) で更新できる形」で持ち、入出力も高速にする必要があります。

そのために、各図書館の在庫を 二重配列（リストのリスト） でそのまま保持し、申請 \((v,d)\) が来たら libs[v][d] を直接更新します。これなら1件あたり定数時間で処理できます。

例：図書館2のジャンル3の在庫が 0 のときに借りようとしても減らせず、失敗回数だけ増えます。

アルゴリズム

1. 入力から \(N\) を読む。
2. 各図書館 \(i\) について、ジャンル数 \(M_i\) と初期在庫 \(S_{i,1..M_i}\) を読み、libs[i] = [S_{i,1}, ..., S_{i,M_i}] として保存する。
3. \(Q\) 件の申請を順に処理する：
   • v, d を 0-index に直す（v-1, d-1）
   • libs[v][d] > 0 なら libs[v][d] -= 1
   • そうでなければ fail += 1
4. 最後に各図書館の配列をスペース区切りで出力し、最終行に fail を出力する。

計算量

• 時間計算量: \(O\!\left(\sum_{i=1}^{N} M_i + Q\right)\)
  （初期在庫の読み込み + 申請を1回ずつ処理）
• 空間計算量: \(O\!\left(\sum_{i=1}^{N} M_i\right)\)
  （全ジャンルの在庫数を保持）

実装のポイント

• 0-index に変換：入力は 1-index なので、v-1, d-1 にして配列アクセスを簡単にします。

• 高速入力：sys.stdin.buffer.read().split() でまとめて読み、iter で順に取り出すと Python でも十分高速です。

• 高速出力：print を大量に呼ぶ代わりに、文字列を配列 out に貯めて最後に "\n".join(out) でまとめて出力します。

  ソースコード

import sys

def main():
    it = iter(map(int, sys.stdin.buffer.read().split()))
    N = next(it)
    libs = []
    for _ in range(N):
        Mi = next(it)
        libs.append([next(it) for _ in range(Mi)])

    Q = next(it)
    fail = 0
    for _ in range(Q):
        v = next(it) - 1
        d = next(it) - 1
        a = libs[v]
        if a[d] > 0:
            a[d] -= 1
        else:
            fail += 1

    out = []
    for a in libs:
        out.append(" ".join(map(str, a)))
    out.append(str(fail))
    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

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