分数: 266 分
问题陈述
高桥是拆弹小组的组长。目前, N 建筑物排成一排,编号 1, 2, \ldots, N 从左到右。每栋楼 i 具有耐久值 H_i.
不幸的是, M 该区域将发生爆炸。的 j建筑物中心发生爆炸 T_j 带电源 D_j。请注意,同一栋建筑物可能是多次爆炸的中心。
当 j发生第次爆炸,会发生以下耐久度降低:
- 建筑物的耐久性 T_j 减少 D_j.
- If T_j \geq 2, 建筑物的耐久性 T_j - 1 减少 \lfloor D_j / 2 \rfloor.
- If T_j \leq N - 1, 建筑物的耐久性 T_j + 1 减少 \lfloor D_j / 2 \rfloor.
在这里, \lfloor D_j / 2 \rfloor 表示除以得到的值 D_j by 2 并向下舍入。每次爆炸最多影响 3 建筑物 - 中心建筑物及其两个邻居 - 不会影响较远的建筑物。
每次爆炸造成的损害均按照上述方式确定,无论建筑物当前的耐久度如何,因此爆炸的顺序 M 发生爆炸并不影响结果。
耐久性值可能会小于 0 (负值)。即使建筑物的耐久性下降到 0 或以下,它不会从行中移除,并继续像往常一样受到后续爆炸的影响(其耐用性可能会进一步降低)。而且,如果这样的建筑物成为爆炸中心,它也会像往常一样影响周围的建筑物。
毕竟 M 爆炸已结束,求最终耐久度为的建筑物数量 1 或更大。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 1 \leq T_j \leq N (1 \leq j \leq M)
- 1 \leq D_j \leq 10^9 (1 \leq j \leq M)
- 所有输入值均为整数
输入
N M H_1 H_2 \ldots H_N T_1 D_1 T_2 D_2 \vdots T_M D_M
- 第一行包含建筑物数量 N 和爆炸次数 M,用空格分隔。
- 第二行包含初始耐久值 每栋建筑的 H_1, H_2, \ldots, H_N ,以空格分隔。
- 以下 M 行包含每次爆炸的信息。
- 的 (2 + j)-第行包含建筑物编号 T_j 那是 j第次爆炸及其威力 D_j,用空格分隔。
输出
单行输出最终耐久度为的建筑物数量 所有爆炸完成后 1 或更高。
示例输入 1
5 2 10 20 30 20 10 3 15 1 8
示例输出 1
5
示例输入 2
7 4 100 50 80 120 60 40 90 2 60 5 100 2 30 7 50
示例输出 2
4
示例输入 3
10 6 500 300 450 200 600 150 400 250 350 100 3 400 7 300 1 600 5 500 10 200 4 100
示例输出 3
4