C - Preparing for a Hot Spring Trip Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は旅行会社で働いており、N 人の顧客の温泉旅行への参加状況を管理しています。顧客にはそれぞれ 1 から N までの番号が付けられています。

各顧客は「旅行ポイント」を持っています。顧客 i の初期の旅行ポイントは A_i であり、旅行ポイントが閾値 T_i 以上であるとき、その顧客は旅行への参加を決定します。

高橋君は Q 回のキャンペーンを順に実施します。j 回目のキャンペーンでは、顧客番号が L_j 以上 R_j 以下であるすべての顧客の旅行ポイントを X_j だけ増加させます。

すべてのキャンペーンが終わった後の最終的な旅行ポイントが閾値以上になっている顧客の人数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq T_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq N
  • 1 \leq X_j \leq 10^9
  • 入力はすべて整数である

入力

N Q
A_1 T_1
A_2 T_2
\vdots
A_N T_N
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_Q R_Q X_Q
  • 1 行目には、顧客の数 N とキャンペーンの回数 Q が、スペース区切りで与えられる。
  • 続く N 行では、各顧客の情報が与えられる。このうち i 行目では、顧客 i の初期旅行ポイント A_i と、参加を決定するポイントの閾値 T_i が、スペース区切りで与えられる。
  • 続く Q 行では、各キャンペーンの情報が与えられる。このうち j 行目では、j 回目のキャンペーンの対象区間の左端 L_j 、右端 R_j 、増加させるポイント X_j が、スペース区切りで与えられる。

出力

すべてのキャンペーンが終わった後に旅行ポイントが閾値以上になっている顧客の人数を 1 行で出力してください。

入力例 1

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

出力例 1

4

入力例 2

3 2
0 100
50 50
99 100
1 3 50
2 2 1

出力例 2

2

入力例 3

10 5
100 500
200 300
0 1000
450 451
999999999 1000000000
0 10
50 100
300 350
0 1
600 700
1 5 100
3 7 500
1 10 50
6 8 20
2 4 150

出力例 3

7

Score : 366 pts

Problem Statement

Takahashi works at a travel agency and manages the participation status of N customers for a hot spring trip. Each customer is assigned a number from 1 to N.

Each customer has "travel points." Customer i initially has A_i travel points, and when their travel points are at least the threshold T_i, that customer decides to participate in the trip.

Takahashi conducts Q campaigns in order. In the j-th campaign, the travel points of all customers whose numbers are between L_j and R_j (inclusive) are increased by X_j.

Determine the number of customers whose final travel points after all campaigns are at least their threshold.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 0 \leq A_i \leq 10^9
  • 1 \leq T_i \leq 10^9
  • 1 \leq L_j \leq R_j \leq N
  • 1 \leq X_j \leq 10^9
  • All input values are integers

Input

N Q
A_1 T_1
A_2 T_2
\vdots
A_N T_N
L_1 R_1 X_1
L_2 R_2 X_2
\vdots
L_Q R_Q X_Q
  • The first line contains the number of customers N and the number of campaigns Q, separated by a space.
  • The following N lines give information about each customer. The i-th of these lines contains customer i's initial travel points A_i and the threshold T_i for deciding to participate, separated by a space.
  • The following Q lines give information about each campaign. The j-th of these lines contains the left endpoint L_j, right endpoint R_j of the target range, and the points to increase X_j for the j-th campaign, separated by spaces.

Output

Print in one line the number of customers whose travel points are at least their threshold after all campaigns have been completed.

Sample Input 1

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

Sample Output 1

4

Sample Input 2

3 2
0 100
50 50
99 100
1 3 50
2 2 1

Sample Output 2

2

Sample Input 3

10 5
100 500
200 300
0 1000
450 451
999999999 1000000000
0 10
50 100
300 350
0 1
600 700
1 5 100
3 7 500
1 10 50
6 8 20
2 4 150

Sample Output 3

7