概要

各申請を順に処理し、各ショップで「定員内なら追加、満員なら最小優先度の会員と比較して入れ替え」を行った結果、最終的な会員数を求める問題です。

考察

このルールは、各ショップごとに見ると「その時点で登録されている会員のうち、優先度が高い方から最大 \(C_j\) 人だけを残す」操作を、申請順にオンラインで行っているのと同じです。

素朴な方法が厳しい理由

ショップ \(d\) が満員のときに「最も優先度が低い会員」を探す必要があります。

• 会員を配列で持って毎回最小を探すと、1回の申請で \(O(C_d)\) かかりうる
  → 最悪で \(Q=2\times10^5\)、\(C_d\) も大きいと \(O(NQ)\) 近くになり TLE になります。
• ソート済み構造を毎回維持しても、挿入・削除のコストを抑える工夫が必要です。

解決の方向性

満員時に必要なのは「現在の最小優先度」だけです。
そこで、各ショップに 最小値を高速に取り出せるデータ構造（最小ヒープ）を持たせれば、

• 最小優先度の取得：\(O(1)\)（ヒープ先頭）
• 追加・入れ替え：\(O(\log C_d)\)

で処理できます。

またこの問題では - 同じ顧客は複数回申請しない - 顧客の優先度はすべて異なる

ので、「一度落とされた顧客が別の申請で復活する」などを考える必要がなく、各ショップを独立に処理できます。

アルゴリズム

各ショップ \(j\) について、(優先度, 顧客ID) を要素とする 最小ヒープ heaps[j] を用意します（ヒープ先頭がそのショップの最小優先度会員）。

申請 \((p, d)\) を処理するとき：

1. \(a = A_p\) を申請者の優先度とする。
2. もし len(heaps[d]) < C_d（まだ空きあり）なら
   
   • heappush(heaps[d], (a, p)) でそのまま登録。
3. そうでなく満員なら、ヒープ先頭 (amin, *) が「最も優先度が低い会員」なので、
   • もし \(amin < a\) なら入れ替え
     heapreplace(heaps[d], (a, p))（最小要素を取り除いて新要素を入れる）
   • それ以外（\(a\) が小さい/同じ）なら却下（何もしない）

最後に各ショップ \(j\) について len(heaps[j]) が最終会員数です。

（例）定員2のショップで現在の優先度が {10, 30}（最小は10）のとき、優先度20が来たら 10 と入れ替えて {20, 30}、優先度5が来たら却下、という動きをヒープで高速に実現します。

計算量

• 時間計算量: \(O\!\left(\sum_{k=1}^{Q} \log C_{D_k}\right) \subseteq O(Q\log N)\)
  （各申請でヒープ操作が高々1回）
• 空間計算量: \(O(N + M)\)
  （ヒープに入る要素の総数は最大でも採用された人数分で \(O(N)\)、ショップ配列が \(O(M)\)）

実装のポイント

• ヒープには (優先度, 顧客ID) を入れますが、比較に本質的に必要なのは優先度だけです（顧客IDは同一優先度が無いのでなくてもよいが、タプルにしておくと扱いやすい）。

• 満員時の「削除して追加」は heappop + heappush でも良いですが、heapreplace を使うと1回で書けて定数倍も小さめです。

• 入力が最大 \(2\times10^5\) なので、sys.stdin.buffer.read() でまとめて読み、整数列として処理すると高速です。

• 最終的に必要なのは各ショップの人数だけなので、ヒープの中身を取り出して並べ替える必要はありません。

  ソースコード

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it); M = next(it); Q = next(it)

    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = next(it)

    C = [0] * (M + 1)
    for j in range(1, M + 1):
        C[j] = next(it)

    heaps = [[] for _ in range(M + 1)]

    for _ in range(Q):
        p = next(it); d = next(it)
        h = heaps[d]
        ap = A[p]
        if len(h) < C[d]:
            heapq.heappush(h, (ap, p))
        else:
            if h[0][0] < ap:
                heapq.heapreplace(h, (ap, p))

    out = [str(len(heaps[j])) for j in range(1, M + 1)]
    sys.stdout.write(" ".join(out))

if __name__ == "__main__":
    main()

---

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