C - プレミアムショップの会員登録 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は、N 人の顧客の会員登録を管理するシステムを運営しています。

それぞれの顧客には 1 から N までの番号が付けられており、顧客 i は優先度 A_i を持っています。すべての顧客の優先度は互いに異なります。優先度の値が大きいほど、優先度が高いものとします。

ショップは M 店舗あり、各ショップには 1 から M までの番号が付けられています。ショップ j には会員枠 C_j が設定されており、そのショップに同時に登録できる会員数の上限を表しています。

はじめ、どの顧客もどのショップにも登録されていません。これから Q 件の申請が順番に処理されます。各顧客が申請を行うのは高々 1 回です（すなわち、異なる申請の申請者はすべて異なります）。k 番目の申請では、顧客 P_k がショップ D_k への会員登録を希望します。

申請が処理されるとき、以下のルールに従います：

  • そのショップの現在の会員数が会員枠 C_{D_k} 未満であれば、顧客 P_k はそのショップの会員として登録されます。
  • そのショップの現在の会員数が会員枠 C_{D_k} に等しい（すなわち満員である）場合、現在そのショップに登録されている会員の中で最も優先度が低い会員と、申請した顧客 P_k の優先度を比較します。すべての顧客の優先度は互いに異なるため、最も優先度が低い会員は一意に定まります。
  • 申請した顧客の優先度の方が高ければ、最も優先度が低い会員の登録は解除され（どのショップにも登録されていない状態に戻ります）、申請した顧客が新たにそのショップの会員として登録されます。
  • そうでなければ（申請した顧客の優先度の方が低ければ）、申請は却下されます。申請した顧客はどのショップにも登録されていない状態のままであり、ショップの会員にも変化はありません。

上記のルールにより、どの時点においても各ショップの会員数は会員枠を超えません。また、各顧客が申請を行うのは高々 1 回であるため、ある顧客が複数のショップに同時に登録されることはありません。

すべての申請の処理が完了した後、各ショップに登録されている会員の人数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • A_i \neq A_j (i \neq j)
  • 1 \leq C_j \leq N (1 \leq j \leq M)
  • 1 \leq P_k \leq N (1 \leq k \leq Q)
  • 1 \leq D_k \leq M (1 \leq k \leq Q)
  • P_k \neq P_l (k \neq l)（すなわち、各顧客が申請を行うのは高々 1 回である）
  • 入力はすべて整数

入力

N M Q
A_1 A_2 \ldots A_N
C_1 C_2 \ldots C_M
P_1 D_1
P_2 D_2
\vdots
P_Q D_Q
  • 1 行目には、顧客の人数 N 、ショップの数 M 、申請の件数 Q が、スペース区切りで与えられる。
  • 2 行目には、各顧客の優先度 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 3 行目には、各ショップの会員枠 C_1, C_2, \ldots, C_M が、スペース区切りで与えられる。
  • 続く Q 行では、各申請の情報が与えられる。
  • 3 + k 行目には、k 番目の申請を行う顧客の番号 P_k と、希望するショップの番号 D_k がスペース区切りで与えられる。

出力

M 個の整数をスペース区切りで 1 行に出力せよ。 j 番目の整数は、ショップ j に最終的に登録されている会員の人数を表す。

入力例 1

5 2 5
10 30 20 50 40
2 1
1 1
2 1
3 1
4 2
5 2

出力例 1

2 1

入力例 2

7 3 7
5 15 25 35 45 55 3
2 2 1
7 1
1 1
3 1
2 2
4 2
5 2
6 3

出力例 2

2 2 1

入力例 3

10 4 10
100 90 80 70 60 50 40 30 20 10
3 2 2 1
8 1
10 1
9 1
7 1
5 2
6 2
3 2
4 3
2 3
1 4

出力例 3

3 2 2 1

Score : 366 pts

Problem Statement

Takahashi operates a system that manages membership registration for N customers.

Each customer is assigned a number from 1 to N, and customer i has a priority A_i. All customers have distinct priorities. A larger priority value means a higher priority.

There are M shops, each numbered from 1 to M. Shop j has a membership capacity C_j, which represents the maximum number of members that can be registered at that shop simultaneously.

Initially, no customer is registered at any shop. From now on, Q applications will be processed in order. Each customer submits at most one application (that is, all applicants across different applications are distinct). In the k-th application, customer P_k requests membership registration at shop D_k.

When an application is processed, the following rules apply:

  • If the current number of members at the shop is less than the capacity C_{D_k}, customer P_k is registered as a member of that shop.
  • If the current number of members at the shop equals the capacity C_{D_k} (i.e., the shop is full), the priority of the applying customer P_k is compared with that of the member currently registered at the shop who has the lowest priority. Since all customers have distinct priorities, the member with the lowest priority is uniquely determined.
  • If the applying customer's priority is higher, the member with the lowest priority is unregistered (returning to a state of not being registered at any shop), and the applying customer is newly registered as a member of that shop.
  • Otherwise (if the applying customer's priority is lower), the application is rejected. The applying customer remains unregistered at any shop, and the shop's members remain unchanged.

By the above rules, the number of members at each shop never exceeds its capacity at any point. Also, since each customer submits at most one application, no customer is ever registered at multiple shops simultaneously.

After all applications have been processed, determine the number of members registered at each shop.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • A_i \neq A_j (i \neq j)
  • 1 \leq C_j \leq N (1 \leq j \leq M)
  • 1 \leq P_k \leq N (1 \leq k \leq Q)
  • 1 \leq D_k \leq M (1 \leq k \leq Q)
  • P_k \neq P_l (k \neq l) (that is, each customer submits at most one application)
  • All input values are integers

Input

N M Q
A_1 A_2 \ldots A_N
C_1 C_2 \ldots C_M
P_1 D_1
P_2 D_2
\vdots
P_Q D_Q
  • The first line contains the number of customers N, the number of shops M, and the number of applications Q, separated by spaces.
  • The second line contains the priorities A_1, A_2, \ldots, A_N of each customer, separated by spaces.
  • The third line contains the membership capacities C_1, C_2, \ldots, C_M of each shop, separated by spaces.
  • The following Q lines contain information about each application.
  • The (3 + k)-th line contains the customer number P_k who submits the k-th application and the desired shop number D_k, separated by a space.

Output

Output M integers separated by spaces on a single line. The j-th integer represents the number of members finally registered at shop j.

Sample Input 1

5 2 5
10 30 20 50 40
2 1
1 1
2 1
3 1
4 2
5 2

Sample Output 1

2 1

Sample Input 2

7 3 7
5 15 25 35 45 55 3
2 2 1
7 1
1 1
3 1
2 2
4 2
5 2
6 3

Sample Output 2

2 2 1

Sample Input 3

10 4 10
100 90 80 70 60 50 40 30 20 10
3 2 2 1
8 1
10 1
9 1
7 1
5 2
6 2
3 2
4 3
2 3
1 4

Sample Output 3

3 2 2 1