A - Bomb Disposal Squad Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は爆弾処理班のリーダーです。現在、N 個の建物が一列に並んでおり、左から順に 1, 2, \ldots, N の番号が付けられています。各建物 i は耐久値 H_i を持っています。

不幸なことに、この地域で M 回の爆発が発生します。j 回目の爆発は、建物 T_j を中心として威力 D_j で発生します。なお、同じ建物が複数回の爆発の中心となることもあり得ます。

j 回目の爆発が発生すると、以下の耐久値の減少が起こります。

  • 建物 T_j の耐久値が D_j 減少する。
  • T_j \geq 2 の場合、建物 T_j - 1 の耐久値が \lfloor D_j / 2 \rfloor 減少する。
  • T_j \leq N - 1 の場合、建物 T_j + 1 の耐久値が \lfloor D_j / 2 \rfloor 減少する。

ここで \lfloor D_j / 2 \rfloor は D_j を 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
  • 1 行目には、建物の数 N と爆発の回数 M が、スペース区切りで与えられる。
  • 2 行目には、各建物の初期耐久値 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
  • 3 行目から M 行にわたり、各爆発の情報が与えられる。
  • 2 + j 行目には、j 回目の爆発の中心となる建物番号 T_j と威力 D_j が、スペース区切りで与えられる。

出力

すべての爆発が終わった後、最終的な耐久値が 1 以上である建物の数を 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

Score : 266 pts

Problem Statement

Takahashi is the leader of a bomb disposal squad. Currently, N buildings are lined up in a row, numbered 1, 2, \ldots, N from left to right. Each building i has a durability value H_i.

Unfortunately, M explosions will occur in this area. The j-th explosion occurs centered at building T_j with power D_j. Note that the same building may be the center of multiple explosions.

When the j-th explosion occurs, the following durability reductions take place:

  • The durability of building T_j decreases by D_j.
  • If T_j \geq 2, the durability of building T_j - 1 decreases by \lfloor D_j / 2 \rfloor.
  • If T_j \leq N - 1, the durability of building T_j + 1 decreases by \lfloor D_j / 2 \rfloor.

Here, \lfloor D_j / 2 \rfloor denotes the value obtained by dividing D_j by 2 and rounding down. Each explosion affects at most 3 buildings — the center building and its two neighbors — and does not affect buildings farther away.

The damage from each explosion is determined as described above regardless of the building's current durability, so the order in which the M explosions occur does not affect the result.

Durability values can become less than 0 (negative values). Even if a building's durability drops to 0 or below, it is not removed from the row and continues to be affected by subsequent explosions as usual (its durability may decrease further). Also, if such a building becomes the center of an explosion, it affects surrounding buildings as usual.

After all M explosions have finished, find the number of buildings whose final durability is 1 or greater.

Constraints

  • 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)
  • All input values are integers

Input

N M
H_1 H_2 \ldots H_N
T_1 D_1
T_2 D_2
\vdots
T_M D_M
  • The first line contains the number of buildings N and the number of explosions M, separated by a space.
  • The second line contains the initial durability values H_1, H_2, \ldots, H_N of each building, separated by spaces.
  • The following M lines contain the information for each explosion.
  • The (2 + j)-th line contains the building number T_j that is the center of the j-th explosion and its power D_j, separated by a space.

Output

Output in a single line the number of buildings whose final durability is 1 or greater after all explosions have finished.

Sample Input 1

5 2
10 20 30 20 10
3 15
1 8

Sample Output 1

5

Sample Input 2

7 4
100 50 80 120 60 40 90
2 60
5 100
2 30
7 50

Sample Output 2

4

Sample Input 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

Sample Output 3

4