概要

各顧客が持つ優先度に基づいて、会員登録の申請を処理し、各ショップに最終的に登録された会員数を求める問題です。

考察

この問題では、各ショップに対して「会員枠」があり、優先度が高い顧客が申請してきたときに、既存の会員の中で最も優先度が低い顧客を追い出す可能性があります。これは典型的な「上位 \(k\) 個の要素を効率的に管理する」タイプの問題であり、優先度付きキュー（ヒープ）を活用することで効率的に処理できます。

素朴なアプローチでは…

• 各ショップの会員をリストで管理し、毎回全探索で最小値を探していたら、最悪ケースで \(O(Q \cdot C_{\max})\) かかり、間に合いません。
• 特に \(C_j\) が大きい場合や \(Q\) が最大 \(2 \times 10^5\) あるため、計算量的に破綻します。

改善策

• 各ショップごとに、最小ヒープを使って現在の会員の中での最小優先度を \(O(\log C_j)\) で取得・更新できるようにします。
• 追加・削除ともに高速に行えるため、全体の処理が高速化されます。
• さらに、顧客IDの存在チェックのために set も併用することで、ある顧客がすでに登録されているかどうかを高速に判定します。

アルゴリズム

1. 各ショップに対して、会員の情報を管理する 最小ヒープ と、顧客IDを保持する set を用意します。
2. 各申請に対して以下のように処理します：
   • 会員枠に空きがあれば、そのまま追加。
   • 会員枠が埋まっていれば：
     • ヒープの先頭（最小優先度の会員）と比較。
     • 申請者の優先度が高ければ、先頭を削除して新しい顧客を追加。
3. 最後に、各ショップの会員数（= set のサイズ）を出力します。

例

例えば、ショップ1の会員枠が2で、優先度が [10, 20] の会員がいるときに、優先度30の顧客が申請した場合： - 最小優先度10の会員を削除し、30の顧客を追加。 - 結果として、ショップ1の会員は [20, 30] になります。

計算量

• 時間計算量: \(O(Q \log N)\)
  • 各申請でヒープ操作（追加 or 削除）が最大1回発生し、それは \(O(\log C_j)\) で、最悪でも \(O(\log N)\)。
• 空間計算量: \(O(N + M)\)
  • 各顧客・ショップに関する情報を保存するのに必要。

実装のポイント

• ヒープには (優先度, 顧客ID) のタプルを入れることで、優先度が同じ場合は自動的に顧客IDで比較されますが、今回は優先度が全て異なるので気にしなくてよいです。
• 顧客IDの存在を set で管理することで、すでに登録済みかどうかを高速に判定できます。
• 入力を高速に読み込むために sys.stdin.read を使用しています。

## ソースコード

```python
import heapq
import sys

input = sys.stdin.read

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    
    A = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = int(data[idx]); idx += 1
    
    C = [0] * (M + 1)
    for j in range(1, M + 1):
        C[j] = int(data[idx]); idx += 1
    
    # 各ショップの会員リスト（優先度の最小ヒープ）
    members = [[] for _ in range(M + 1)]
    # 各ショップの会員セット（顧客IDの存在確認用）
    member_set = [set() for _ in range(M + 1)]
    
    for _ in range(Q):
        P = int(data[idx]); idx += 1
        D = int(data[idx]); idx += 1
        
        if len(member_set[D]) < C[D]:
            # 会員枠に空きがある場合
            heapq.heappush(members[D], (A[P], P))
            member_set[D].add(P)
        else:
            # 会員枠が満杯の場合
            if members[D]:
                min_priority, min_customer = members[D][0]
                if A[P] > min_priority:
                    # 最低優先度の会員を削除
                    heapq.heappop(members[D])
                    member_set[D].discard(min_customer)
                    # 新しい会員を追加
                    heapq.heappush(members[D], (A[P], P))
                    member_set[D].add(P)
            # それ以外は却下
    
    result = []
    for j in range(1, M + 1):
        result.append(str(len(member_set[j])))
    
    print(' '.join(result))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。