C - Discount Coupon Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、 N 個の商品を購入しようとしています。商品には 1 から N までの番号が付いており、商品 i の価格は W_i 円です。

高橋君は Q 枚の割引クーポンを持っています。 j 枚目のクーポンは、番号が L_j 以上 R_j 以下であるすべての商品（すなわち商品 L_j, L_j+1, \ldots, R_j）に対して、それぞれの価格を D_j 円割り引く効果があります。

同じ商品に複数のクーポンが適用される場合、割引額はすべて累積します。すなわち、商品 i に対して適用されるすべてのクーポンの割引額の合計を S_i とすると、すべてのクーポンを適用した後の商品 i の価格は \max(W_i - S_i,\ 0) 円になります。

すべてのクーポンを適用した後、価格が 0 円になった商品（すなわち W_i \leq S_i を満たす商品）の個数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq W_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq N
  • 1 \leq D_j \leq 10^9
  • 入力はすべて整数

入力

N Q
W_1 W_2 \ldots W_N
L_1 R_1 D_1
L_2 R_2 D_2
\vdots
L_Q R_Q D_Q
  • 1 行目には、商品の個数を表す N と、クーポンの枚数を表す Q が、スペース区切りで与えられる。
  • 2 行目には、各商品の初期価格を表す W_1, W_2, \ldots, W_N が、スペース区切りで与えられる。
  • 3 行目から Q 行にわたって、各クーポンの情報が与えられる。
  • 2 + j 行目には、 j 枚目のクーポンの対象区間の左端 L_j 、右端 R_j 、割引額 D_j が、スペース区切りで与えられる。

出力

すべてのクーポンを適用した後、価格が 0 円になった商品の個数を 1 行で出力してください。

入力例 1

5 3
100 200 150 300 50
1 3 100
2 4 150
5 5 50

出力例 1

4

入力例 2

7 4
500 300 200 400 100 600 250
1 4 200
3 5 150
2 6 100
4 7 300

出力例 2

5

入力例 3

10 6
1000000000 500 200 800 1200 300 450 100 900 600
1 5 600
3 7 250
1 3 400
6 10 400
2 8 200
5 9 500

出力例 3

8

Score : 366 pts

Problem Statement

Takahashi is about to purchase N items. The items are numbered from 1 to N, and the price of item i is W_i yen.

Takahashi has Q discount coupons. The j-th coupon has the effect of discounting the price of every item whose number is between L_j and R_j inclusive (i.e., items L_j, L_j+1, \ldots, R_j) by D_j yen each.

When multiple coupons apply to the same item, the discount amounts are all accumulated. That is, if the total discount amount from all coupons applied to item i is S_i, then the price of item i after applying all coupons becomes \max(W_i - S_i,\ 0) yen.

After applying all coupons, find the number of items whose price becomes 0 yen (i.e., items satisfying W_i \leq S_i).

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq W_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq N
  • 1 \leq D_j \leq 10^9
  • All input values are integers.

Input

N Q
W_1 W_2 \ldots W_N
L_1 R_1 D_1
L_2 R_2 D_2
\vdots
L_Q R_Q D_Q
  • The first line contains N, the number of items, and Q, the number of coupons, separated by a space.
  • The second line contains the initial prices of the items W_1, W_2, \ldots, W_N, separated by spaces.
  • The following Q lines contain the information for each coupon.
  • The (2 + j)-th line contains the left endpoint L_j, right endpoint R_j, and discount amount D_j of the j-th coupon, separated by spaces.

Output

Print in one line the number of items whose price becomes 0 yen after applying all coupons.

Sample Input 1

5 3
100 200 150 300 50
1 3 100
2 4 150
5 5 50

Sample Output 1

4

Sample Input 2

7 4
500 300 200 400 100 600 250
1 4 200
3 5 150
2 6 100
4 7 300

Sample Output 2

5

Sample Input 3

10 6
1000000000 500 200 800 1200 300 450 100 900 600
1 5 600
3 7 250
1 3 400
6 10 400
2 8 200
5 9 500

Sample Output 3

8