分数: 266 分
问题陈述
高桥是一家物流中心的经理,负责监督 N 仓库。每个仓库的存储容量都有上限。
各仓库 i (1 \leq i \leq N) 当前存储 W_i 公斤货物,其容量限制为 L_i 公斤。情况不一定是这样 W_i \leq L_i 处于初始状态;可能有些仓库已经超出其容量限制。
共 M 装载/卸载操作将按顺序进行。在 j第一次操作 (1 \leq j \leq M),更改 仓库出现 C_j 公斤 P_j。如果 C_j 为正数,代表正在加载(货物增加);如果 C_j 为负数,代表卸货(货物减少);如果 C_j = 0,表示没有变化。可以对同一个仓库执行多个操作。
即使仓库中的货物数量超过其容量限制或在操作期间或之后变为负值,操作仍会继续而不会中断。即使最终货物数量为负数,产能过剩检查仍照常进行。
所有操作完成后,确定需要的仓库数量 容量过剩。仓库 如果仓库中的最终货物数量 i 超出容量 i 严格大于 L_i (如果等于 L_i,未超容量)。该确定仅基于所有操作完成后的最终货物数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 0 \leq W_i \leq 10^9
- 1 \leq L_i \leq 10^9
- 有可能 W_i > L_i
- 1 \leq P_j \leq N
- -10^9 \leq C_j \leq 10^9 (包括案例 C_j = 0)
- 所有输入值均为整数
输入
N M W_1 L_1 W_2 L_2 \vdots W_N L_N P_1 C_1 P_2 C_2 \vdots P_M C_M
- 第一行包含两个空格分隔的整数: N,仓库数量,以及 M,操作次数。
- 行 2 通过 N + 1 给出每个仓库的信息。
- 线 1 + i 包含当前商品数量 W_i 和容量限制 仓库 L_i 仓库的 i,用空格分隔。
- 行 N + 2 通过 N + M + 1 给出每个操作的信息(如果 M = 0).
- 线 N + 1 + j 包含目标仓库编号 P_j 及货物变更 C_j for the j第一个操作,以空格分隔。
输出
在一行上打印所有操作完成后超出容量的仓库数量。
示例输入 1
3 4 50 100 80 100 30 50 1 30 2 25 3 15 2 10
示例输出 1
1
示例输入 2
5 6 100 200 150 150 0 100 200 300 50 80 2 10 3 50 5 20 1 150 3 60 5 15
示例输出 2
4
示例输入 3
10 12 500000000 1000000000 999999999 1000000000 0 100 750000000 800000000 100 100 0 1000000000 123456789 500000000 999999998 999999999 50 50 1000000000 1000000000 1 500000001 2 2 4 100000000 5 1 9 1 7 400000000 3 -50 8 5 6 1000000000 10 1 3 200 4 -50000000
示例输出 3
8