G. Distinctification
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: 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\); 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)\).
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.
Print \(n\) integers — the \(i\)-th number should be equal to \(f(P_i)\).