I - 蟻と角砂糖 (Ants and Sugar) Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

JOI-kun is a biologist. He plans an experiment on ants and sugar.

JOI-kun’s experiment takes place on a long straight stick of length 1\,000\,000\,000 (= 10^{9}). It is placed from the left to the right. The point on the stick which is located at a distance x from the leftmost point is called the point of coordinate x.

Now, nothing is placed on the stick. JOI-kun will perform the Q operations. The i-th operation (1 \le i \le Q) is specified by the three integers T_{i}, X_{i}, A_{i}. They mean as follows.

  • If T_{i} = 1, JOI-kun places A_{i} ants at the point of coordinate X_{i}.
  • If T_{i} = 2, JOI-kun places A_{i} sugar cubes at the point of coordinate X_{i}.

Since ants and sugar cubes are very small, it is possible to place some of them at the same point. JOI-kun may perform several operations at the same point.

The ants used in this experiment have curious properties. Precisely, if JOI-kun claps hands, every ant will do the following.

  • If there is a sugar cube at a distance less than or equal to L from the ant, the ant will choose any one of them and eat it.

It may happen that several ants eat the same sugar cube at the same time.

For every k (1 \le k \le Q), JOI-kun wants to know the answer to the following question.

  • Assume that JOI-kun claps hands after the k-th operation. What is the maximum possible number of sugar cubes eaten by at least one ant?

Write a program which, given the operations performed by JOI-kun and the value of L, answers to JOI-kun’s questions for all k.

Note that JOI-kun does not clap hands actually. Therefore, the positions of the ants do not change, and the sugar cubes are not eaten.

Input

Read the following data from the standard input. Given values are all integers.

Q L
T_{1} X_{1} A_{1}
T_{2} X_{2} A_{2}
\vdots
T_{Q} X_{Q} A_{Q}

Output

Write Q lines to the standard output. The k-th line (1 \le k \le Q) of output should contain the maximum possible number of sugar cubes eaten by at least one ant if JOI-kun claps hands after the k-th operation.

Constraints

  • 1 \le Q \le 500\,000.
  • 1 \le L \le 1\,000\,000\,000 (= 10^{9}).
  • T_{i} is 1 or 2 (1 \le i \le Q).
  • 0 \le X_{i} \le 1\,000\,000\,000 (= 10^{9}) (1 \le i \le Q).
  • 1 \le A_{i} \le 1\,000\,000\,000 (= 10^{9}) (1 \le i \le Q).

Subtasks

  1. (6 points) Q \le 3\,000.
  2. (16 points) L = 1, X_{i} \le Q - 1, X_{i} + T_{i} is an even integer (1 \le i \le Q).
  3. (26 points) Q is an even integer, T_{i} = 1 (1 \le i \le Q/2), T_{i} = 2 (Q/2 + 1 \le i \le Q).
  4. (52 points) No additional constraints.

Sample Input and Output

Sample Input 1

4 1
1 1 1
2 2 1
1 3 1
2 0 1

Sample Output 1

0
1
1
2

In this sample input, the operations and the answer to the question for each k are as follows.

  1. JOI-kun places an ant at the point of coordinate 1. Assume that JOI-kun claps hands. Since there is no sugar cube, the answer to the question for k = 1 is 0.
  2. JOI-kun places a sugar cube at the point of coordinate 2. Assume that JOI-kun claps hands. Then, the ant of coordinate 1 eats the sugar cube of coordinate 2. Therefore, the answer to the question for k = 2 is 1.
  3. JOI-kun places an ant at the point of coordinate 3. Assume that JOI-kun claps hands. Then, both of the ants of coordinates 1, 3 eat the sugar cube of coordinate 2. Therefore, the answer to the question for k = 3 is 1.
  4. JOI-kun places a sugar cube at the point of coordinate 0. Assume that JOI-kun claps hands. The number of sugar cubes eaten by at least one ant becomes maximum if the ant of coordinates 1 eats the sugar cube of coordinate 0 and the ant of coordinates 3 eats the sugar cube of coordinate 2. Therefore, the answer to the question for k = 4 is 2.

This sample input satisfies the constraints of Subtasks 1, 2, 4.

Sample Input 2

20 1
2 16 778913911
1 7 558407445
1 1 589762439
1 17 74646747
1 1 149104909
1 15 956697952
2 6 389372991
2 4 867453845
1 15 157353445
1 9 846177695
1 7 747107163
2 10 525670462
2 16 478912944
2 6 301733761
2 12 132966485
1 1 748012313
2 10 830922632
1 19 969484637
1 13 370330582
1 1 464798040

Sample Output 2

0
0
0
74646747
74646747
778913911
1168286902
1168286902
1168286902
1168286902
1168286902
1693957364
2103741597
2405475358
2405475358
2405475358
2725982591
2725982591
2858949076
2858949076

This sample input satisfies the constraints of Subtasks 1, 2, 4.

Sample Input 3

20 6
2 27 12
2 9 11
1 36 10
2 39 4
2 14 9
2 33 7
2 38 20
2 0 20
2 25 16
1 14 3
1 13 19
2 6 4
2 15 6
2 33 4
1 12 11
1 44 1
2 17 14
2 12 19
1 48 18
2 30 16

Sample Output 3

0
0
0
4
4
10
10
10
10
13
30
30
32
32
40
41
44
44
44
44

This sample input satisfies the constraints of Subtasks 1, 4.

Sample Input 4

20 268886972
1 984472666 733463744
1 478477245 94817772
1 242536956 330762563
1 65794782 319137646
1 320548477 937296140
1 815011370 938193848
1 565184190 917533785
1 245417414 534089975
1 529908772 977043962
1 603891865 700935654
2 167042244 479827216
2 173921297 798343455
2 916159596 810126726
2 999299355 465535307
2 965968070 501768990
2 936073643 174976034
2 832859952 778072072
2 955489596 704853861
2 246733786 382428992
2 227669861 390905006

Sample Output 4

0
0
0
0
0
0
0
0
0
0
479827216
1278170671
2088297397
2553832704
2949828263
2949828263
3727900335
3727900335
4110329327
4501234333

This sample input satisfies the constraints of Subtasks 1, 3, 4.

配点 : 100 点

問題文

生物学者の JOI 君は,蟻と角砂糖を使った実験を計画している.

JOI 君の実験は,左右に横たわる長さ 1\,000\,000\,000 (= 10^{9}) の細長いまっすぐな棒の上で行われる.棒の左端から右方向に距離 x 進んだ点を,座標 x の点と呼ぶことにする.

現在,棒の上には何も存在しない.これから JOI 君は,Q 回の操作を行う .i 回目 (1 \leqq i \leqq Q) の操作は 3 つの整数 T_{i}, X_{i}, A_{i} で表され,以下の操作を行うことを意味する.

  • T_{i} = 1 のとき:JOI 君が座標 X_{i} の点に A_{i} 匹の蟻を置く.
  • T_{i} = 2 のとき:JOI 君が座標 X_{i} の点に A_{i} 個の角砂糖を置く.

なお,蟻や角砂糖は非常に小さいため,同じ座標にそれらが複数個存在することは可能である.また,同じ座標に対して複数回操作することもありうる.

ところで,実験で使う蟻には不思議な特性がある.具体的には,JOI 君が手を叩くと,それぞれの蟻は以下の動作を一度だけ行う.

  • 自分との距離が L 以下の角砂糖が存在するなら,その中から 1 つを自由に選び,それを食べる.

なお,複数の蟻が同じ 1 つの角砂糖を食べることもありうる.

JOI 君は,すべての k (1 \leqq k \leqq Q) について,以下の質問の答えを知りたい.

  • k 回目の操作が終わった段階で手を叩いた場合,最大で何個の角砂糖が 1 匹以上の蟻に食べられるか.

JOI 君が行う操作の情報および L の値が与えられるので,すべての k について JOI 君の質問に答えるプログラムを作成せよ.

なお,実際には操作の途中で手を叩くことはないため,蟻の位置は操作の間で変化せず,また角砂糖が食べられることもない.

入力

入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.

Q L
T_{1} X_{1} A_{1}
T_{2} X_{2} A_{2}
\vdots
T_{Q} X_{Q} A_{Q}

出力

標準出力に Q 行で出力せよ .k 行目 (1 \leqq k \leqq Q) には,k 回目の操作が終わった段階で手を叩いた場合,最大で何個の角砂糖が 1 匹以上の蟻に食べられるかを出力せよ.

制約

  • 1 \leqq Q \leqq 500\,000.
  • 1 \leqq L \leqq 1\,000\,000\,000 (= 10^{9}).
  • T_{i} は 1 または 2 である (1 \leqq i \leqq Q).
  • 0 \leqq X_{i} \leqq 1\,000\,000\,000 (= 10^{9}) (1 \leqq i \leqq Q).
  • 1 \leqq A_{i} \leqq 1\,000\,000\,000 (= 10^{9}) (1 \leqq i \leqq Q).

小課題

  1. (6 点) Q \leqq 3\,000.
  2. (16 点) L = 1,X_{i} \leqq Q - 1,X_{i} + T_{i} は偶数 (1 \leqq i \leqq Q).
  3. (26 点) Q は偶数,T_{i} = 1 (1 \leqq i \leqq Q/2),T_{i} = 2 (Q/2 + 1 \leqq i \leqq Q).
  4. (52 点) 追加の制約はない.

入出力例

入力例 1

4 1
1 1 1
2 2 1
1 3 1
2 0 1

出力例 1

0
1
1
2

この入力例では,一連の操作の内容,およびそれぞれの k に対する質問の答えは以下のようになる.

  1. 座標 1 に 1 匹の蟻を置く.この時点で手を叩いた場合,角砂糖は存在しないため,k = 1 の場合の質問の答えは 0 になる.
  2. 座標 2 に 1 個の角砂糖を置く.この時点で手を叩いた場合,座標 1 の蟻が座標 2 の角砂糖を食べるため,k = 2 の場合の質問の答えは 1 になる.

  3. 座標 3 に 1 匹の蟻を置く.この時点で手を叩いた場合,座標 1, 3 の蟻は両方とも座標 2 の角砂糖を食べるため,k = 3 の場合の質問の答えは 1 になる.

  4. 座標 0 に 1 個の角砂糖を置く.この時点で手を叩いた場合,座標 1 の蟻が座標 0 の角砂糖を,座標 3 の蟻が座標 2 の角砂糖を食べるときに,食べられる角砂糖の個数が最大となる.よって,k = 4 の場合の質問の答えは 2 になる.

この入力例は小課題 1, 2, 4 の制約を満たす.

入力例 2

20 1
2 16 778913911
1 7 558407445
1 1 589762439
1 17 74646747
1 1 149104909
1 15 956697952
2 6 389372991
2 4 867453845
1 15 157353445
1 9 846177695
1 7 747107163
2 10 525670462
2 16 478912944
2 6 301733761
2 12 132966485
1 1 748012313
2 10 830922632
1 19 969484637
1 13 370330582
1 1 464798040

出力例 2

0
0
0
74646747
74646747
778913911
1168286902
1168286902
1168286902
1168286902
1168286902
1693957364
2103741597
2405475358
2405475358
2405475358
2725982591
2725982591
2858949076
2858949076

この入力例は小課題 1, 2, 4 の制約を満たす.

入力例 3

20 6
2 27 12
2 9 11
1 36 10
2 39 4
2 14 9
2 33 7
2 38 20
2 0 20
2 25 16
1 14 3
1 13 19
2 6 4
2 15 6
2 33 4
1 12 11
1 44 1
2 17 14
2 12 19
1 48 18
2 30 16

出力例 3

0
0
0
4
4
10
10
10
10
13
30
30
32
32
40
41
44
44
44
44

この入力例は小課題 1, 4 の制約を満たす.

入力例 4

20 268886972
1 984472666 733463744
1 478477245 94817772
1 242536956 330762563
1 65794782 319137646
1 320548477 937296140
1 815011370 938193848
1 565184190 917533785
1 245417414 534089975
1 529908772 977043962
1 603891865 700935654
2 167042244 479827216
2 173921297 798343455
2 916159596 810126726
2 999299355 465535307
2 965968070 501768990
2 936073643 174976034
2 832859952 778072072
2 955489596 704853861
2 246733786 382428992
2 227669861 390905006

出力例 4

0
0
0
0
0
0
0
0
0
0
479827216
1278170671
2088297397
2553832704
2949828263
2949828263
3727900335
3727900335
4110329327
4501234333

この入力例は小課題 1, 3, 4 の制約を満たす.


Source Name

JOI 2021/2022 春合宿 Contest Day3 問題3