Background

JOISC2022 D3T3

Problem Description

Mr. JOI is a biologist. He is going to do some experiments on ants and sugar cubes.

Mr. JOI’s experiment is carried out on a wooden stick of length $10^9$. This stick is placed from left to right. The point whose distance from the left endpoint is $x$ is called the point with coordinate $x$.

At the beginning, there is nothing on the stick. Mr. JOI will perform $Q$ operations. The $i$-th operation $(1 \le i \le Q)$ is described by three integers $T_i, X_i, A_i$, meaning:

• If $T_i = 1$, Mr. JOI places $A_i$ ants at the point with coordinate $X_i$.
• If $T_i = 2$, Mr. JOI places $A_i$ sugar cubes at the point with coordinate $X_i$.

Since both ants and sugar cubes are very small, it is possible that some ants and sugar cubes are placed at the same point. Mr. JOI may also perform multiple operations at the same point.

The ants used in this experiment are very “curious”. Specifically, when Mr. JOI claps his hands, each ant performs the following action:

• If there exists a sugar cube whose distance from the ant is at most $L$, it chooses any one of them and eats it.

It is possible that multiple ants eat the same sugar cube at the same time.

For each $k$ $(1 \le k \le Q)$, Mr. JOI wants to know the answer to the following question.

• Suppose Mr. JOI claps his hands once after the $k$-th operation. What is the maximum number of sugar cubes that are eaten by at least one ant?

Write a program that, given the operations performed by Mr. JOI and the value of $L$, answers Mr. JOI’s question for all $k$.

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

Input Format

The first line contains two positive integers $Q, L$, representing the number of operations and the range within which an ant may eat a sugar cube.

The next $Q$ lines describe the operations. The $i$-th line $(1 \le i \le Q)$ contains three integers $T_i, X_i, A_i$, representing one operation.

Output Format

Output $Q$ lines. The $k$-th line $(1 \le k \le Q)$ contains one integer, representing the maximum possible number of sugar cubes that would be eaten by at least one ant if Mr. JOI claps his hands once after the $k$-th operation.

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

0
1
1
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

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

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

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

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

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

Hint

[Sample Explanation #1]

In this sample, all operations and the answer for each $k$ are as follows:

1. Mr. JOI places one ant at coordinate $1$.
   Since there are no sugar cubes, the answer is $0$.
2. Mr. JOI places one sugar cube at coordinate $2$.
   If Mr. JOI claps now, the ant at coordinate $1$ will eat the sugar cube at coordinate $2$, so the answer is $1$.
3. Mr. JOI places one ant at coordinate $3$.
   If Mr. JOI claps now, the ants at coordinates $1$ and $3$ will eat the sugar cube at coordinate $2$ at the same time, so the answer is $1$.
4. Mr. JOI places one sugar cube at coordinate $0$.
   If Mr. JOI claps now, the ants at coordinates $1$ and $3$ can eat the sugar cubes at coordinates $0$ and $2$ respectively, so the answer is $2$.

This sample satisfies the constraints of subtasks $1, 2, 4$.

[Sample Explanation #2]

This sample satisfies the constraints of subtasks $1, 2, 4$.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks $1, 4$.

[Sample Explanation #4]

This sample satisfies the constraints of subtasks $1, 3, 4$.

[Constraints]

For all testdata, it holds that:

• $1 \le Q \le 500\,000$.
• $1 \le L \le 10^9$.
• $T_i \in \{1, 2\}$.
• $0 \le X_i \le 10^9$ $(1 \le i \le Q)$.
• $1 \le A_i \le 10^9$ $(1 \le i \le Q)$.

The additional constraints and scores for the subtasks are shown in the table below:

Translated by ChatGPT 5