← 返回题目列表

AtCoder · awc0109_c

C. 在高级商店注册会员

中文机器翻译题面 查看原题

分数: 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