Nikita and stack
Contest: 8VC Venture Cup 2017 - Final Round
Difficulty rating: 2200
Tags: data structures

Nikita has a stack. A stack in this problem is a data structure that supports two operations. Operation push(x) puts an integer x on the top of the stack, and operation pop() deletes the top integer from the stack, i. e. the last added. If the stack is empty, then the operation pop() does nothing.

Nikita made m operations with the stack but forgot them. Now Nikita wants to remember them. He remembers them one by one, on the i-th step he remembers an operation he made pi-th. In other words, he remembers the operations in order of some permutation p1, p2, ..., pm. After each step Nikita wants to know what is the integer on the top of the stack after performing the operations he have already remembered, in the corresponding order. Help him!

Input format:
The first line contains the integer m (1 ≤ m ≤ 105) — the number of operations Nikita made.

The next m lines contain the operations Nikita remembers. The i-th line starts with two integers pi and ti (1 ≤ pi ≤ m, ti = 0 or ti = 1) — the index of operation he remembers on the step i, and the type of the operation. ti equals 0, if the operation is pop(), and 1, is the operation is push(x). If the operation is push(x), the line also contains the integer xi (1 ≤ xi ≤ 106) — the integer added to the stack.

It is guaranteed that each integer from 1 to m is present exactly once among integers pi.

Output format:
Print m integers. The integer i should equal the number on the top of the stack after performing all the operations Nikita remembered on the steps from 1 to i. If the stack is empty after performing all these operations, print -1.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, after Nikita remembers the operation on the first step, the operation push(2) is the only operation, so the answer is 2. After he remembers the operation pop() which was done before push(2), answer stays the same.

In the second example, the operations are push(2), push(3) and pop(). Nikita remembers them in the order they were performed.

In the third example Nikita remembers the operations in the reversed order.

Example input:
2
2 1 2
1 0

Example output:
2
2

Example input:
3
1 1 2
2 1 3
3 0

Example output:
2
3
2

Editorial:
Hint 1: look at the operations in the reverse order. Let's count the balance for each prefix, i.e. the difference between the number of push(x) operations and the number of pop() operations.
Hint 2: Now we have to find the first operation that makes balance positive. This can be done using segment tree.
Solution: Let's reverse the order of operations. Now we can see that on the top of the stack will be the first integer added with push(x) such that the number of pop() operations and the number of push(x) operations before this operation is equal, if there is one. Let's keep for each position a value called balance: the number of push(x) operations minus the number of pop() operations before and including this position. To find the answer, we should find the first position with posivive balance. When we add an operation, we should add -1 or 1 to all posisions starting with the position of the operation, depending on the type of the operation.
To cope with the operations quickly, we can store the balance in a segment tree. The addition is done with lazy propogation, finding the first position with positive balance can be done in two ways. First way is to perform binary search on the answer and then query the segment tree for maximim on some prefix. The compexity is $${\mathcal O}(\log^{2}m)$$ per query then. The other way is to walk down the tree always moving to the leftmost son with positive maximum. When we reach the leaf, the position of this leaf is the answer. The complexity is $$O(\log m)$$ per query.
The overall complexity is $${ \mathcal { O } } ( m \log m )$$ or $${\mathcal {O}}(m\log ^{2}m)$$ depending on the realization.