C - Watering the Flower Bed Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は学校の園芸委員会で、花壇の管理を担当しています。

花壇には N 株の花が一列に植えられており、左から順に花 1、花 2、…、花 N と番号が付けられています。各花 i には品種ごとに定められた許容水分量 S_i があります。

高橋君はこれから M 回の水やり作業を行います。水やり作業を行う前の時点では、どの花もまだ水を受け取っていません。j 回目の作業では、花 L_j から花 R_j までのすべての花に、それぞれ水量 W_j の水を与えます。

すべての水やり作業が終了した後、花 i が受け取った水の総量（すなわち、花 i に対して行われたすべての水やり作業で与えられた水量の合計）が許容水分量 S_i より真に大きい場合、花 i は「根腐れ」を起こします。許容水分量以下であれば根腐れは起こしません。

根腐れを起こした花の株数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq S_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 W_j \leq 10^9 (1 \leq j \leq M)
  • 入力はすべて整数

入力

N M
S_1 S_2 \ldots S_N
L_1 R_1 W_1
L_2 R_2 W_2
\vdots
L_M R_M W_M
  • 1 行目には、花の株数を表す N と、水やり作業の回数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各花の許容水分量 S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
  • 続く M 行のうち j 行目には、j 回目の作業で水を与える範囲の左端 L_j、右端 R_j、および各花に与える水量 W_j が、スペース区切りで与えられる。

出力

すべての水やり作業終了後に根腐れを起こした花の株数を 1 行で出力せよ。

入力例 1

5 2
10 5 8 12 3
1 3 4
2 5 6

出力例 1

3

入力例 2

7 4
15 20 10 25 30 5 18
1 4 8
3 6 12
2 5 5
4 7 10

出力例 2

3

入力例 3

10 6
100 50 80 120 60 90 40 110 70 55
1 5 30
3 8 25
6 10 35
2 4 40
5 7 20
1 10 10

出力例 3

4

Score : 366 pts

Problem Statement

Takahashi is in charge of managing the flower bed as part of the school's gardening committee.

The flower bed has N flowers planted in a row, numbered flower 1, flower 2, …, flower N from left to right. Each flower i has a moisture tolerance S_i determined by its species.

Takahashi will perform M watering operations. Before any watering operation is performed, no flower has received any water. In the j-th operation, he gives water of amount W_j to each of the flowers from flower L_j to flower R_j.

After all watering operations are completed, if the total amount of water received by flower i (that is, the sum of the water amounts given to flower i across all watering operations) is strictly greater than its moisture tolerance S_i, then flower i suffers "root rot." If the total amount is less than or equal to the moisture tolerance, root rot does not occur.

Find the number of flowers that suffer root rot.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq S_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 W_j \leq 10^9 (1 \leq j \leq M)
  • All inputs are integers

Input

N M
S_1 S_2 \ldots S_N
L_1 R_1 W_1
L_2 R_2 W_2
\vdots
L_M R_M W_M
  • The first line contains N, the number of flowers, and M, the number of watering operations, separated by a space.
  • The second line contains the moisture tolerances S_1, S_2, \ldots, S_N of each flower, separated by spaces.
  • In the following M lines, the j-th line contains the left endpoint L_j, the right endpoint R_j of the range of flowers to water in the j-th operation, and the amount of water W_j given to each flower, separated by spaces.

Output

Print on a single line the number of flowers that suffer root rot after all watering operations are completed.

Sample Input 1

5 2
10 5 8 12 3
1 3 4
2 5 6

Sample Output 1

3

Sample Input 2

7 4
15 20 10 25 30 5 18
1 4 8
3 6 12
2 5 5
4 7 10

Sample Output 2

3

Sample Input 3

10 6
100 50 80 120 60 90 40 110 70 55
1 5 30
3 8 25
6 10 35
2 4 40
5 7 20
1 10 10

Sample Output 3

4