C - Streetlights and Blizzard Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は街の管理者です。大通りには N 本の街灯が一列に並んでおり、左から順に街灯 1, 街灯 2, \ldots, 街灯 N と番号が付けられています。街灯 i (1 \leq i \leq N) の初期耐久値は H_i です。耐久値が 0 以下になった街灯は倒壊したものとみなされます。

この冬、M 回の吹雪がやってきます。j 回目 (1 \leq j \leq M) の吹雪は、街灯 L_j から街灯 R_j までの範囲に含まれるすべての街灯の耐久値を D_j だけ減少させます。

各街灯の最終的な耐久値は、初期耐久値からすべての吹雪で受けた減少量の合計を引いた値となります。すなわち、途中で耐久値が 0 以下になったとしても、その後の吹雪による減少が免除されることはありません。

すべての吹雪が過ぎ去った後、最終的な耐久値が 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 L_j \leq R_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
L_1 R_1 D_1
L_2 R_2 D_2
\vdots
L_M R_M D_M
  • 1 行目には、街灯の本数 N と吹雪の回数 M が、スペース区切りで与えられる。
  • 2 行目には、各街灯の初期耐久値 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
  • 続く M 行にわたって、各吹雪の情報が与えられる。j 行目には、j 回目の吹雪が影響を及ぼす範囲の左端 L_j、右端 R_j、および耐久値の減少量 D_j がスペース区切りで与えられる。

出力

すべての吹雪が過ぎ去った後、最終的な耐久値が 1 以上である街灯の本数を 1 行で出力せよ。

入力例 1

5 2
10 5 8 3 7
2 4 3
1 3 4

出力例 1

3

入力例 2

3 2
3 2 1
1 3 2
1 1 1

出力例 2

0

入力例 3

10 5
100 50 30 80 60 40 90 20 70 10
1 5 20
3 8 15
6 10 25
1 10 10
2 4 30

出力例 3

5

入力例 4

15 6
1000000000 500 300 800 600 400 900 200 700 100 550 350 750 450 1000000000
1 15 100
1 8 200
5 12 150
3 10 50
7 15 100
1 15 50

出力例 4

10

入力例 5

1 1
1
1 1 1

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi is the manager of a city. Along the main street, N street lights are lined up in a row, numbered from left to right as street light 1, street light 2, \ldots, street light N. The initial durability of street light i (1 \leq i \leq N) is H_i. A street light whose durability becomes 0 or less is considered to have collapsed.

This winter, M blizzards will come. The j-th blizzard (1 \leq j \leq M) decreases the durability of all street lights in the range from street light L_j to street light R_j by D_j.

The final durability of each street light is its initial durability minus the total decrease from all blizzards. That is, even if a street light's durability becomes 0 or less partway through, it is not exempt from the decreases caused by subsequent blizzards.

After all blizzards have passed, determine the number of street lights whose final durability is 1 or more (i.e., that have not collapsed).

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 L_j \leq R_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
L_1 R_1 D_1
L_2 R_2 D_2
\vdots
L_M R_M D_M
  • The first line contains the number of street lights N and the number of blizzards M, separated by a space.
  • The second line contains the initial durabilities H_1, H_2, \ldots, H_N of each street light, separated by spaces.
  • The following M lines provide information about each blizzard. The j-th line contains the left endpoint L_j, right endpoint R_j of the range affected by the j-th blizzard, and the durability decrease D_j, separated by spaces.

Output

Print in one line the number of street lights whose final durability is 1 or more after all blizzards have passed.

Sample Input 1

5 2
10 5 8 3 7
2 4 3
1 3 4

Sample Output 1

3

Sample Input 2

3 2
3 2 1
1 3 2
1 1 1

Sample Output 2

0

Sample Input 3

10 5
100 50 30 80 60 40 90 20 70 10
1 5 20
3 8 15
6 10 25
1 10 10
2 4 30

Sample Output 3

5

Sample Input 4

15 6
1000000000 500 300 800 600 400 900 200 700 100 550 350 750 450 1000000000
1 15 100
1 8 200
5 12 150
3 10 50
7 15 100
1 15 50

Sample Output 4

10

Sample Input 5

1 1
1
1 1 1

Sample Output 5

0