C - 花壇の水やり 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は学校の園芸委員会の委員長です。学校には N 個の花壇があり、それぞれの花壇には 1 から N までの番号が付けられています。

各花壇 i (1 \leq i \leq N) には初期水分量 L_i が設定されています。花壇の水分量が K 以上であれば花は元気に育ちますが、K 未満になると花は枯れてしまいます。高橋君は花を元気に保つために、これから M 回の水やりを行います。

j 回目 (1 \leq j \leq M) の水やりでは、花壇 X_j から花壇 Y_j まで（X_j \leq Y_j）の連続した番号の花壇すべてに対して、水分量を Z_j だけ増加させます。水やり以外の要因で水分量が変化することはありません。

すべての水やりが終わった後、各花壇の最終的な水分量は、初期水分量にすべての水やりによる増加分を加えた値になります。最終的な水分量が K 以上である花壇の個数、すなわち高橋君が元気に保てた花壇の個数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq 10^9
  • 0 \leq L_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq X_j \leq Y_j \leq N (1 \leq j \leq M)
  • 1 \leq Z_j \leq 10^4 (1 \leq j \leq M)
  • 入力はすべて整数である

入力

N M K
L_1 L_2 \ldots L_N
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_M Y_M Z_M
  • 1 行目には、花壇の個数 N、水やりの回数 M、花が元気に育つために必要な水分量の基準値 K が、スペース区切りで与えられる。
  • 2 行目には、各花壇の初期水分量 L_1, L_2, \ldots, L_N が、スペース区切りで与えられる。
  • 続く M 行には、各水やりの情報が与えられる。M = 0 の場合、この部分は存在しない。
  • 2 + j 行目 (1 \leq j \leq M) には、j 回目の水やりにおける対象範囲の開始花壇番号 X_j、終了花壇番号 Y_j、水分量の増加量 Z_j が、スペース区切りで与えられる。

出力

すべての水やりが終わった後、最終的な水分量が K 以上である花壇の個数を 1 行で出力せよ。

入力例 1

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

出力例 1

3

入力例 2

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

出力例 2

6

入力例 3

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

出力例 3

7

Score : 366 pts

Problem Statement

Takahashi is the head of the school's gardening committee. The school has N flower beds, each numbered from 1 to N.

Each flower bed i (1 \leq i \leq N) has an initial moisture level L_i. If a flower bed's moisture level is at least K, the flowers grow healthily, but if it falls below K, the flowers wilt. To keep the flowers healthy, Takahashi will perform M watering operations.

In the j-th watering operation (1 \leq j \leq M), he increases the moisture level by Z_j for all consecutively numbered flower beds from flower bed X_j to flower bed Y_j (X_j \leq Y_j). The moisture levels do not change due to any factors other than watering.

After all watering operations are completed, the final moisture level of each flower bed is the initial moisture level plus the total increase from all watering operations. Find the number of flower beds whose final moisture level is at least K, that is, the number of flower beds that Takahashi was able to keep healthy.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq K \leq 10^9
  • 0 \leq L_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq X_j \leq Y_j \leq N (1 \leq j \leq M)
  • 1 \leq Z_j \leq 10^4 (1 \leq j \leq M)
  • All input values are integers

Input

N M K
L_1 L_2 \ldots L_N
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_M Y_M Z_M
  • The first line contains the number of flower beds N, the number of watering operations M, and the threshold moisture level K required for flowers to grow healthily, separated by spaces.
  • The second line contains the initial moisture levels L_1, L_2, \ldots, L_N of each flower bed, separated by spaces.
  • The following M lines contain information about each watering operation. If M = 0, this part does not exist.
  • The (2 + j)-th line (1 \leq j \leq M) contains the starting flower bed number X_j, the ending flower bed number Y_j, and the moisture increase amount Z_j for the j-th watering operation, separated by spaces.

Output

Print in one line the number of flower beds whose final moisture level is at least K after all watering operations are completed.

Sample Input 1

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

Sample Output 1

3

Sample Input 2

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

Sample Output 2

6

Sample Input 3

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

Sample Output 3

7