分数: 366 分
问题陈述
高桥运营一个管理会员注册的系统 N 客户。
为每个客户分配一个号码 1 to N和客户 i 有优先权 A_i。所有客户都有不同的优先事项。优先级值越大,优先级越高。
有 M 商店,每个编号从 1 to M。商店 j 拥有会员资格 C_j,代表该店铺可同时注册的最大会员人数。
最初,没有顾客在任何商店注册。从现在开始, Q 申请将按顺序处理。每个客户最多提交一份申请(即不同申请中的所有申请人都是不同的)。在 k第一个应用程序,客户 P_k 要求在商店注册会员 D_k.
处理申请时,适用以下规则:
- 如果店铺当前会员人数少于容量 C_{D_k},客户 P_k 已注册为该商店的会员。
- 如果店铺当前会员人数等于容量 C_{D_k} (即店铺已满),申请客户的优先级 P_k 与当前在商店注册的优先级最低的会员进行比较。由于所有客户都有不同的优先级,因此优先级最低的成员是唯一确定的。
- 如果申请顾客的优先级较高,则优先级最低的会员被取消注册(返回到未在任何商店注册的状态),并且申请顾客被重新注册为该商店的会员。
- 否则(如果申请客户的优先级较低),申请将被拒绝。申请顾客在任何商店均未注册,且该商店的会员保持不变。
根据上述规则,每个商店的会员数量在任何时候都不会超过其容量。此外,由于每个顾客最多提交一份申请,因此不会有顾客同时在多个商店注册。
处理完所有申请后,确定每个商店注册的会员人数。
约束
- 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) (即每个客户最多提交一份申请)
- 所有输入值均为整数
输入
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
- 第一行包含客户数量 N, 店铺数量 M,以及申请数量 Q,用空格分隔。
- 第二行包含优先级 每个客户的 A_1, A_2, \ldots, A_N ,以空格分隔。
- 第三行包含会员资格 每个商店的 C_1, C_2, \ldots, C_M ,以空格分隔。
- 以下 Q 行包含有关每个应用程序的信息。
- 的 (3 + k)第行包含客户编号 P_k 谁提交 k第一个申请和所需的店铺号 D_k,用空格分隔。
输出
输出 M 单行上用空格分隔的整数。 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