P9528 [JOIST 2022] Ants and Sugar / Ants and Sugar

JOISC2022 D3T3

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.

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 $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.

**[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: |Subtask ID|Additional Constraints|Score| |:-:|:-:|:-:| |$1$|$Q \le 3\,000$|$6$| |$2$|$L = 1$, $X_i \le Q - 1$, and $X_i + T_i$ is even $(1 \le i \le Q)$|$16$| |$3$|$Q$ is even, $T_i = 1$ $(1 \le i \le Q/2)$, $T_i = 2$ $(Q/2 + 1 \le i \le Q)$|$26$| |$4$|No additional constraints|$52$| Translated by ChatGPT 5