Variable Damage
Contest: Educational Codeforces Round 170 (Rated for Div. 2)
Difficulty rating: 3000
Tags: data structures, flows

Monocarp is gathering an army to fight a dragon in a videogame.

The army consists of two parts: the heroes and the defensive artifacts. Each hero has one parameter — his health. Each defensive artifact also has one parameter — its durability.

Before the battle begins, Monocarp distributes artifacts to the heroes so that each hero receives at most one artifact.

The battle consists of rounds that proceed as follows:

- first, the dragon deals damage equal to $$$\frac{1}{a + b}$$$ (a real number without rounding) to each hero, where $$$a$$$ is the number of heroes alive and $$$b$$$ is the number of active artifacts;
- after that, all heroes with health $$$0$$$ or less die;
- finally, some artifacts are deactivated. An artifact with durability $$$x$$$ is deactivated when one of the following occurs: the hero holding the artifact either dies or receives $$$x$$$ total damage (from the start of the battle). If an artifact is not held by any hero, it is inactive from the beginning of the battle.

The battle ends when there are no heroes left alive.

Initially, the army is empty. There are $$$q$$$ queries: add a hero with health $$$x$$$ or an artifact with durability $$$y$$$ to the army. After each query, determine the maximum number of rounds that Monocarp can survive if he distributes the artifacts optimally.

Input format:
The first line contains one integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

In the $$$i$$$-th of the following $$$q$$$ lines, there are two integers $$$t_i$$$ and $$$v_i$$$ ($$$t_i \in \{1, 2\}$$$; $$$1 \le v_i \le 10^9$$$) — the type of the query and the value of the query parameter. If the type is $$$1$$$, a hero with health $$$v_i$$$ is added. If the type is $$$2$$$, an artifact with durability $$$v_i$$$ is added.

Output format:
Print $$$q$$$ integers. After each query, output the maximum number of rounds that Monocarp can survive if he distributes the artifacts optimally.

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
Let's consider the first example.

- An artifact with durability $$$5$$$ is added. Since there are no heroes yet, the battle ends immediately.
- A hero with health $$$4$$$ is added. Monocarp can give him an artifact with durability $$$5$$$. First, there are rounds in which the hero takes $$$\frac{1}{1 + 1} = \frac{1}{2}$$$ damage. After $$$8$$$ such rounds, a total of $$$4$$$ damage will have been dealt, and the hero will die, while the artifact will deactivate. There are no more heroes alive, so the battle ends after $$$8$$$ rounds.
- A hero with health $$$10$$$ is added. Now let the artifact with durability $$$5$$$ be with this hero. Then, in the first $$$12$$$ rounds, the heroes will take $$$12 \cdot \frac{1}{2 + 1} = 4$$$ damage, and the first hero will die. The second hero has $$$6$$$ health left, and the artifact has $$$1$$$ durability. Now the damage is $$$\frac{1}{2}$$$, so after another $$$2$$$ rounds, the artifact will deactivate. The second hero has $$$5$$$ health left. After another $$$5$$$ rounds, the second hero will die. Therefore, the answer is $$$12 + 2 + 5 = 19$$$.

Example input:
3
2 5
1 4
1 10

Example output:
0
8
19

Example input:
10
1 9
1 6
2 4
1 8
1 3
2 10
1 3
1 6
1 10
2 6

Example output:
9
15
19
27
30
39
42
48
59
65

Editorial:
Let's start unraveling the solution from the end. Suppose we currently have $$$n$$$ heroes with health $$$a_1, a_2, \dots, a_n$$$ and $$$m$$$ artifacts with durability $$$b_1, b_2, \dots, b_m$$$. Let's assume we have already distributed the artifacts to the heroes, forming pairs $$$(a_i, b_i)$$$. If $$$m > n$$$, we will discard the excess artifacts with the lowest durability. If $$$m < n$$$, we will add the artifacts with durability $$$0$$$ (that will deactivate at the start).
How many rounds will the battle last? Notice the following: a hero with health $$$a$$$ and an artifact with durability $$$b$$$ can be replaced with two heroes with health $$$a$$$ and $$$\min(a, b)$$$, respectively, and the answer will not change.
Thus, it is sufficient to analyze the case when there are no artifacts, and there are only heroes with health $$$a_1, \min(a_1, b_1), a_2, \min(a_2, b_2), \dots, a_n, \min(a_n, b_n)$$$. The idea is as follows: in each round, the heroes take exactly $$$1$$$ point of damage in total. Therefore, the battle will last $$$\displaystyle \sum_{i=1}^n a_i + \sum_{i=1}^n \min(a_i, b_i)$$$ rounds. The first sum is easy to maintain —let's focus on the second one.
Next, we need to learn how to distribute the artifacts in such a way that maximizes this sum. Intuitively, it seems that the healthiest heroes should receive the most durable artifacts. That is, we should sort the heroes in descending order of health and the artifacts in descending order of durability.
We will show that this is indeed the case. Suppose there are two heroes with health $$$a_1$$$ and $$$a_2$$$ ($$$a_1 \ge a_2$$$). They receive artifacts with durability $$$b_1$$$ and $$$b_2$$$ ($$$b_1 \ge b_2$$$). We will show that it is optimal to give the first artifact to the first hero and the second one to the second hero. If there is at least one artifact with durability not greater than $$$a_2$$$ (that is, the minimum will always be equal to this artifact), it is always optimal to give it to the second hero and the other artifact to the first hero. If there is at least one artifact with durability not less than $$$a_1$$$ (that is, the minimum will always be equal to the hero), it is always optimal to give it to the first hero. Otherwise, the durabilities of the artifacts lie between the health values of the heroes, meaning that the minimum for the first hero will always be equal to his artifact, and the minimum for the second hero will be his health. Therefore, it is again optimal to give the larger artifact to the first hero. It follows that if for a pair of heroes the condition that the larger hero has the larger artifact is not met, we can swap their artifacts, and the answer will not decrease.
Thus, the task is as follows. After each query, we need to maintain a sorted sequence of heroes, artifacts, and the sum $$$\min(a_i, b_i)$$$. This sounds quite complicated because there are a lot of changes with each query. Some suffix of one of the arrays shifts one position to the right after inserting a new element, affecting many terms.
Let's consider an idea of a sweep line instead. We will combine the heroes and artifacts into one array and sort it in descending order. For simplicity, let's assume all durability and health values are distinct integers. Then we will iterate over this array while maintaining the number of heroes who have not yet received an artifact and the number of artifacts that have not been assigned to a hero. If we encounter an artifact and there are previously encountered heroes who have not received an artifact, we will give this artifact to any of them. Since all these heroes have health greater than the durability of this artifact, the minimum will always be equal to the durability of the artifact. Thus, the sum will increase by the durability of the artifact. Otherwise, we will remember that there is one more free artifact. The same goes for a hero. If we encounter a hero and there are previously encountered artifacts that have not been assigned to a hero, we will give any of these artifacts to the hero. The sum will then increase by the hero's health.
It can be shown that this process of assigning artifacts yields the same result as sorting.
Note that at any moment of time, there are either no free heroes or no free artifacts. Thus, it is sufficient to maintain a "balance" —the difference between the number of heroes and artifacts on the prefix. If the balance is positive, and we encounter an artifact, we add its durability to the answer. If the balance is negative, and we encounter a hero, we add his health to the answer.
Note that equal elements do not break this algorithm. For simplicity, I suggest sorting not just the values but pairs of values and query indices to maintain a strict order.
How does this reduction help? It turns out that it is now possible to use square root decomposition to solve the problem.
Read all queries in advance and sort them by the value $$$(v_i, i)$$$ in descending order. We will divide all queries into blocks of size $$$B$$$. Initially, all queries are deactivated. When processing the next query in the input order, we will activate it within the block and recalculate the entire block.
What should we store for each block? Notice that all balance checks for the terms depend on two values: the balance at the start of the block and the balance before this term within the block. Therefore, for the block, we can maintain the following values: the total balance in the block, as well as the total contribution of the terms from this block for each balance at the start of the block. Obviously, the balance at the start of the block can range from $$$-q$$$ to $$$q$$$. However, if the absolute value of the balance exceeds $$$B$$$, the contribution of the block will be the same as if this balance was limited by $$$-B$$$ or $$$B$$$, respectively (since within the block it will either always be positive or always negative). Thus, it is sufficient to calculate the answer only for balances from $$$-B$$$ to $$$B$$$.
Knowing these values for each block, the answer can be calculated in $$$O(\frac{q}{B})$$$. We will go through the blocks while maintaining the current balance. We will add the block's contribution for the current balance to the answer and add the total balance of the block to the current balance.
We still need to learn how to quickly recalculate the answers for all balances within the block. We will iterate over the elements within the block while maintaining the current balance inside the block. Let the balance be $$$k$$$. Then if the current element is an artifact, its durability will be added to the sum if the balance at the start of the block is at least $$$-k + 1$$$. Similarly, if the current element is a hero, his health will be added if the balance at the start of the block is at most $$$-k - 1$$$. Thus, we need to add a value over some range of balances—either from $$$-k + 1$$$ to $$$B$$$, or from $$$-B$$$ to $$$-k - 1$$$. This can be done using a difference array. That is, we can make two updates in $$$O(1)$$$ for each element of the block, and then compute the prefix sum once in $$$O(B)$$$.
Therefore, for each query, we can update the structure in $$$O(B)$$$, and recalculate the sum in $$$O(\frac{q}{B})$$$. Hence, it is optimal to choose $$$B = \sqrt{q}$$$.
Overall complexity: $$$O(q \sqrt{q})$$$.