問われているのは各ショップに登録されている会員の人数です。人数だけが問われている(更に言うと、「誰であるか」の情報は捨てて良い)ことに注意してください。

人数だけを追跡すると、以下のことが分かります。

• あるショップ \(i\) について、会員枠 \(C_i\) 未満の人数の会員が存在するとき、そこに申請が来ると会員数が \(1\) 増える。
• あるショップ \(i\) について、会員枠 \(C_i\) と同じ人数の会員が存在するとき、誰か \(1\) 人が会員を解除され \(1\) 人が新たに会員になるか、申請が却下されるかのどちらかであるが、どちらにせよ会員数は変化しない。

このことから、ショップ \(i\) に全体で \(X_i\) 件の申請が来た場合、そのショップの会員数は \(\min(C_i,X_i)\) と求められます。

\(X_i\) はバケットソートの要領で求められ、全体の時間計算量は \(O(N+M+Q)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int N,M,Q;
  cin >> N >> M >> Q;
  vector<int> A(N),C(M);
  for(auto &nx : A){cin >> nx;}
  for(auto &nx : C){cin >> nx;}
  vector<int> bk(M,0);
  while(Q--){
    int P,D;
    cin >> P >> D;
    bk[D-1]++;
  }
  for(int i=0;i<M;i++){
    if(i){cout << " ";}
    cout << min(bk[i],C[i]);
  }
  cout << "\n";
  return 0;
}