D - 花壇の水やり 解説 /

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

配点 : 400 点

問題文

高橋君は花壇の管理を担当しています。花壇には N 株の花が一列に植えられており、左から順に花 1 , 花 2 , \ldots , 花 N と番号が付けられています。

各花には「乾燥度」と呼ばれる非負整数の値があり、花 i の初期乾燥度は F_i です。乾燥度が高い花ほど枯れやすいため、水やりが必要になります。

高橋君は M 回の水やり作業を順に行います。j 番目の作業（ j = 1, 2, \ldots, M ）では、花 L_j から花 R_j までのすべての花に水を与え、それらの花の乾燥度をそれぞれ D_j だけ減少させます。

具体的には、花 i （ L_j \leq i \leq R_j ）の乾燥度が現在 v であるとき、この作業により \max(v - D_j,\ 0) に更新されます。すなわち、乾燥度は 0 未満にはなりません。

すべての水やり作業が終わった後、乾燥度が閾値 T 以下になった花は「元気な状態」と見なされ、きれいに咲き続けることができます。一方、乾燥度が T より大きいままの花は依然として枯れるリスクが高い状態です。

青木君は高橋君の水やり計画を見て「元気にできない花がたくさんあるだろう」と言いますが、高橋君は自分の計画に自信を持っています。

高橋君の計画が実行された後、元気な状態になっている花（すなわち最終的な乾燥度が T 以下である花）の株数を求めてください。

制約

  • 1 \leq N \leq 5 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq T \leq 10^9
  • 0 \leq F_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 T
F_1 F_2 \ldots F_N
L_1 R_1 D_1
L_2 R_2 D_2
\vdots
L_M R_M D_M
  • 1 行目には、花の株数 N 、水やり作業の回数 M 、元気な状態と見なす乾燥度の閾値 T が、スペース区切りで与えられる。
  • 2 行目には、各花の初期乾燥度 F_1, F_2, \ldots, F_N が、スペース区切りで与えられる。
  • 続く M 行にわたって、各水やり作業の情報が与えられる。
  • そのうち j 行目（入力全体の 2 + j 行目）には、 j 番目の作業の対象区間の左端 L_j 、右端 R_j 、乾燥度の減少量 D_j が、スペース区切りで与えられる。

出力

すべての水やり作業後に元気な状態（最終的な乾燥度が T 以下）である花の株数を 1 行で出力せよ。

入力例 1

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

出力例 1

5

入力例 2

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

出力例 2

2

入力例 3

10 6 5
0 12 7 20 5 9 14 3 18 6
1 5 4
4 10 6
2 7 3
8 9 10
1 10 1
6 6 5

出力例 3

9

入力例 4

30 18 100
150 80 220 0 95 310 500 120 75 640 130 90 1000 45 260 330 10 700 85 400 55 600 140 20 900 110 70 350 480 5
1 10 50
5 15 80
12 30 60
3 3 200
18 25 300
1 30 20
7 14 100
20 30 150
2 28 10
16 16 5
1 1 1000
10 22 40
23 27 500
4 19 30
8 8 70
29 30 10
6 24 90
13 17 200

出力例 4

24

入力例 5

1 0 1000000000
1000000000

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is in charge of managing a flower bed. The flower bed has N flowers planted in a row, numbered flower 1, flower 2, \ldots, flower N from left to right.

Each flower has a non-negative integer value called "dryness level," and the initial dryness level of flower i is F_i. Flowers with higher dryness levels are more likely to wilt, so they need watering.

Takahashi performs M watering operations in order. In the j-th operation (j = 1, 2, \ldots, M), he waters all flowers from flower L_j to flower R_j, decreasing each of their dryness levels by D_j.

Specifically, if flower i (L_j \leq i \leq R_j) currently has a dryness level of v, this operation updates it to \max(v - D_j,\ 0). In other words, the dryness level never goes below 0.

After all watering operations are completed, flowers whose dryness level is at most the threshold T are considered to be in a "healthy state" and can continue to bloom beautifully. On the other hand, flowers whose dryness level remains greater than T are still at high risk of wilting.

Aoki looks at Takahashi's watering plan and says, "There will probably be many flowers you can't make healthy," but Takahashi is confident in his plan.

After Takahashi's plan is executed, find the number of flowers that are in a healthy state (i.e., flowers whose final dryness level is at most T).

Constraints

  • 1 \leq N \leq 5 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 0 \leq T \leq 10^9
  • 0 \leq F_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 T
F_1 F_2 \ldots F_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 flowers N, the number of watering operations M, and the dryness level threshold T for being considered healthy, separated by spaces.
  • The second line contains the initial dryness levels F_1, F_2, \ldots, F_N of each flower, separated by spaces.
  • The following M lines contain the information for each watering operation.
  • The j-th of these lines (the (2 + j)-th line of the entire input) contains the left endpoint L_j, right endpoint R_j of the target interval, and the dryness level decrease D_j for the j-th operation, separated by spaces.

Output

Output in one line the number of flowers that are in a healthy state (final dryness level is at most T) after all watering operations are completed.

Sample Input 1

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

Sample Output 1

5

Sample Input 2

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

Sample Output 2

2

Sample Input 3

10 6 5
0 12 7 20 5 9 14 3 18 6
1 5 4
4 10 6
2 7 3
8 9 10
1 10 1
6 6 5

Sample Output 3

9

Sample Input 4

30 18 100
150 80 220 0 95 310 500 120 75 640 130 90 1000 45 260 330 10 700 85 400 55 600 140 20 900 110 70 350 480 5
1 10 50
5 15 80
12 30 60
3 3 200
18 25 300
1 30 20
7 14 100
20 30 150
2 28 10
16 16 5
1 1 1000
10 22 40
23 27 500
4 19 30
8 8 70
29 30 10
6 24 90
13 17 200

Sample Output 4

24

Sample Input 5

1 0 1000000000
1000000000

Sample Output 5

1