← 返回题目列表

AtCoder · awc0080_a

A. 拆弹小队

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

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