Distinctification
Contest: Educational Codeforces Round 51 (Rated for Div. 2)
Difficulty rating: 2900
Tags: data structures, dsu, greedy

Suppose you are given a sequence $$$S$$$ of $$$k$$$ pairs of integers $$$(a_1, b_1), (a_2, b_2), \dots, (a_k, b_k)$$$.

You can perform the following operations on it:

1. Choose some position $$$i$$$ and increase $$$a_i$$$ by $$$1$$$. That can be performed only if there exists at least one such position $$$j$$$ that $$$i \ne j$$$ and $$$a_i = a_j$$$. The cost of this operation is $$$b_i$$$;
2. Choose some position $$$i$$$ and decrease $$$a_i$$$ by $$$1$$$. That can be performed only if there exists at least one such position $$$j$$$ that $$$a_i = a_j + 1$$$. The cost of this operation is $$$-b_i$$$.

Each operation can be performed arbitrary number of times (possibly zero).

Let $$$f(S)$$$ be minimum possible $$$x$$$ such that there exists a sequence of operations with total cost $$$x$$$, after which all $$$a_i$$$ from $$$S$$$ are pairwise distinct.

Now for the task itself ...

You are given a sequence $$$P$$$ consisting of $$$n$$$ pairs of integers $$$(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$$$. All $$$b_i$$$ are pairwise distinct. Let $$$P_i$$$ be the sequence consisting of the first $$$i$$$ pairs of $$$P$$$. Your task is to calculate the values of $$$f(P_1), f(P_2), \dots, f(P_n)$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the number of pairs in sequence $$$P$$$.

Next $$$n$$$ lines contain the elements of $$$P$$$: $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$, $$$1 \le b_i \le n$$$). It is guaranteed that all values of $$$b_i$$$ are pairwise distinct.

Output format:
Print $$$n$$$ integers — the $$$i$$$-th number should be equal to $$$f(P_i)$$$.

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

Example input:
5
1 1
3 3
5 5
4 2
2 4

Example output:
0
0
0
-5
-16

Example input:
4
2 4
2 3
2 2
1 1

Example output:
0
3
7
1

Editorial:
Let's firstly try to come up with some naive solution.
Suppose we have a list $$$S$$$ and want to calculate $$$f(S)$$$ for it. Let's sort this list, comparing the pairs by their values of $$$a_i$$$, and then process them one-by-one. We will divide this list into some parts (we will call them components) with the following process: when processing the first pair in the sorted order, let's iterate on the next pairs (also in the sorted order) and add them to the first pair's component until the following condition is met: $$$a_y - a_x > y - x$$$, where $$$x$$$ is the index of the first pair we added, and $$$y$$$ is the index of the pair we are currently trying to add to $$$x$$$'s component (remember that we consider all these pairs in the sorted order).
What is the meaning of this condition? $$$a_y - a_x \le y - x$$$ means that the number of pairs between $$$x$$$ and $$$y$$$ (including these two) is not less that the number of integers in $$$[a_x, a_y]$$$ — and while this condition is met, we can use the first operation in order to make a pair having $$$a_i = z$$$ for every $$$z \in [x, y]$$$. And the first time when the condition $$$a_y - a_x > y - x$$$ is met, we obviously cannot "expand" the segment in such a way. It means that the $$$a$$$-value of $$$y$$$ will always be greater than $$$a$$$-value of $$$x$$$, and $$$y$$$ won't belong to the same component with $$$x$$$ (and will start creating its own component instead).
These components we form have one special property. Suppose we "expanded" the component so that there are no two equal values of $$$a_i$$$ in it. Then we may reorder the pairs in this component as we wish (to do so, we may "contract" the component using the second operation, and then "expand" it again). Of course, the best course of action is to sort the pairs in the component by their values of $$$b_i$$$ in descending order. After doing this for every component, we will obtain an optimal configuration such that all values of $$$a_i$$$ are distinct, and it's easy to calculate the answer.
Okay, now we need to do it fast. The following will help us:
• DSU;
• Some implicit logarithmic data structure (the operations we need are "count the sum of elements less than $$$x$$$" and "count the number of elements greater than $$$y$$$"; your implementation might use other operations);
• Small-to-large merging.
DSU will help us maintain the components. A data structre will be built for each component containing the values of $$$b_i$$$ in it; it will help us to maintain the sum of $$$opt(i) b_i$$$, where $$$opt(i)$$$ is the optimal index of $$$b_i$$$ in this component. Depending on your implementation, you may or may not need to store the minimum value of $$$a_i$$$ in the component. When inserting some element having $$$b_i = b$$$ into some component, the elements having $$$b_i > b$$$ don't change their position, the new element will be added right after them, and the remaining elements will be shifted to the right; so the sum of $$$opt(i) b_i$$$ can be maintained if we query the number of elements greater than $$$b$$$ and the sum of elements less than $$$b$$$.
Okay, but we still don't know how we create the components and how we determine if two components are to merge. We will keep these components in "expanded" form; that is, when processing a pair $$$(a_i, b_i)$$$, let's find the leftmost unoccupied position after $$$a_i$$$ (or $$$a_i$$$, if it is not occupied) and occupy it with the new pair, creating a new component for it. If the newly occupied index is $$$pos$$$, let's try to merge new component with components occupying $$$pos - 1$$$ and $$$pos + 1$$$ (if there are any); to merge two components, do the required operations in DSU and unite the data structures built in these components with small-to-large method.
All this works in $$$O(n \log^2 n)$$$, the most time-consuming part is merging the data structures.