C - Watering the Flower Bed Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、庭にある花壇の管理を任されています。花壇には N 本の花が一列に植えられており、左から順に花 1, 花 2, \ldots, 花 N と番号が付けられています。水やりを始める前の時点で、花 i の高さは H_i です。

高橋君は M 日間にわたって水やりを行います。j 日目（j = 1, 2, \ldots, M）には、花 L_j, L_j + 1, \ldots, R_j に水をやります。水をやられた花は、1 本あたり高さが W_j だけ増加します。

M 日間の水やりがすべて終わった後の花 i の高さを、花 i の最終的な高さと呼びます。花 i の最終的な高さが目標の高さ T_i 以上であるとき、花 i は「十分に成長した」とみなされます。

十分に成長した花の本数を求めてください。

制約

  • 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 T_i \leq 10^{18}（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
H_1 H_2 \ldots H_N
T_1 T_2 \ldots T_N
L_1 R_1 W_1
L_2 R_2 W_2
\vdots
L_M R_M W_M
  • 1 行目には、花の本数を表す整数 N と、水やりの日数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目には、各花の水やり前の高さを表す整数 H_1, H_2, \ldots, H_N が、スペース区切りで与えられる。
  • 3 行目には、各花の目標の高さを表す整数 T_1, T_2, \ldots, T_N が、スペース区切りで与えられる。
  • 続く M 行のうち j 行目には、j 日目に水をやる区間の左端 L_j、右端 R_j、および水やりによって 1 本あたり増加する高さ W_j が、スペース区切りで与えられる。

出力

十分に成長した花の本数を 1 行で出力せよ。

入力例 1

5 3
10 20 30 40 50
25 35 50 40 80
1 3 5
2 4 10
1 5 3

出力例 1

2

入力例 2

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

出力例 2

4

入力例 3

10 5
1000000000 500000000 1 999999999 100 200 300 400 500 600
1000000000000000000 1000000000 100 2000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 10 1000000000
1 5 1000000000
3 8 1000000000
1 10 1000000000
5 10 1000000000

出力例 3

9

Score : 366 pts

Problem Statement

Takahashi is in charge of managing a flower bed in his garden. The flower bed has N flowers planted in a row, numbered flower 1, flower 2, \ldots, flower N from left to right. Before watering begins, the height of flower i is H_i.

Takahashi waters the flowers over M days. On day j (j = 1, 2, \ldots, M), he waters flowers L_j, L_j + 1, \ldots, R_j. Each watered flower increases in height by W_j per flower.

The height of flower i after all M days of watering are completed is called the final height of flower i. Flower i is considered "sufficiently grown" if its final height is at least the target height T_i.

Find the number of sufficiently grown flowers.

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 T_i \leq 10^{18} (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 input values are integers.

Input

N M
H_1 H_2 \ldots H_N
T_1 T_2 \ldots T_N
L_1 R_1 W_1
L_2 R_2 W_2
\vdots
L_M R_M W_M
  • The first line contains an integer N representing the number of flowers and an integer M representing the number of watering days, separated by a space.
  • The second line contains integers H_1, H_2, \ldots, H_N representing the heights of the flowers before watering, separated by spaces.
  • The third line contains integers T_1, T_2, \ldots, T_N representing the target heights of the flowers, separated by spaces.
  • The j-th of the following M lines contains the left endpoint L_j, the right endpoint R_j of the interval to be watered on day j, and the height increase per flower W_j from watering, separated by spaces.

Output

Output the number of sufficiently grown flowers in a single line.

Sample Input 1

5 3
10 20 30 40 50
25 35 50 40 80
1 3 5
2 4 10
1 5 3

Sample Output 1

2

Sample Input 2

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

Sample Output 2

4

Sample Input 3

10 5
1000000000 500000000 1 999999999 100 200 300 400 500 600
1000000000000000000 1000000000 100 2000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1 10 1000000000
1 5 1000000000
3 8 1000000000
1 10 1000000000
5 10 1000000000

Sample Output 3

9