Multiset Queries :
Difficulty Level : Medium
Submissions : 148
Asked In :
Marks :15
: 1 | : 1
Takahashi has many balls, on which nothing is written, and one bag. Initially, the bag is empty. Takahashi will do $$$Q$$$ operations, each of which is of one of the following three types:
- Type $$$1$$$: Write an integer $$$X_i$$$ on a blank ball and put it in the bag.
- Type $$$2$$$: For each ball in the bag, replace the integer written on it with that integer plus $$$X_i$$$.
- Type $$$3$$$: Pick up the ball with the smallest integer in the bag (if there are multiple such balls, pick up one of them). Record the integer written on this ball and throw it away.
For each $$$1 \le i \le Q$$$, you are given the type $$$P_i$$$ of the $$$i-th$$$ operation and the value of $$$X_i$$$ if the operation is of Type $$$1$$$ or $$$2$$$. Print the integers recorded in the operations of Type $$$3$$$ in order.
The first line contains an integer $$$Q$$$ $$$(1 \le Q \le 2 \cdot 10^5)$$$ — the number of queries.
The next $$$Q$$$ lines describe the queries. $$$(1 \le P_i \le 3)$$$ and $$$(1 \le X_i \le 10^9)$$$.
If $$$P_i=3$$$, the bag contains at least one ball just before the $$$i-th$$$ operation.
For each operation with $$$P_i=3$$$ among the $$$Q$$$ operations, print the recorded integer in its own line.
5 1 3 1 5 3 2 2 3
3 7
Takahashi will do the following operations.
- Write $$$3$$$ on a ball and put it in the bag.
- Write $$$5$$$ on a ball and put it in the bag.
- The bag now contains a ball with $$$3$$$ and another with $$$5$$$. Pick up the ball with the smaller of them, or $$$3$$$. Record $$$3$$$ and throw it away.
- The bag now contains just a ball with $$$5$$$. Replace this integer with $$$5+2=7$$$.
- The bag now contains just a ball with $$$7$$$. Pick up this ball, record $$$7$$$, and throw it away.
Therefore, we should print $$$3$$$ and $$$7$$$, in the order they are recorded.
