No.618 labo-index
タグ : / 解いたユーザー数 40
作問者 :
n_knuu
/ テスター :
夕叢霧香(ゆうむらきりか)
Background
(You may skip this part without any problem.)You have mastered the path of research and are now able to open your own laboratory. Congratulations!
While running a laboratory, new researchers may join, and others may leave.
The morale of the whole laboratory may also rise thanks to acquired research funding, or fall because of a scandal.
So, first of all, you have decided to simulate various scenarios of running the laboratory.
Problem Statement
Suppose that a value called a researcher's research power is represented by an integer.
The labo-index $L$ of a laboratory is defined as the largest non-negative integer $l$ satisfying the following condition.
Condition: The laboratory has at least $l$ researchers whose research power is at least $l$.
For example, in a laboratory with $5$ researchers whose research powers are $1, 2, 3, 4, 5$, the labo-index of this laboratory is $L=3$.
If the laboratory has no researchers, its labo-index is $L=0$.
Initially, the laboratory has $0$ researchers.
Then, $Q$ events occur in order, each being one of the following 3 types.
- A researcher with research power $x$ joins the laboratory.
- The researcher who was the $x$-th from the beginning to join the laboratory leaves the laboratory.
- The research power of everyone in the laboratory changes by $+x$.
Input
Q t_1 x_1 t_2 x_2 : t_Q x_Q
$t_i$ represents the type of the $i$-th $(1 \le i \le Q)$ event.
When $t_i=1$, this is an event in which a researcher with research power $x_i$ joins the laboratory.
When $t_i=2$, this is an event in which the researcher who was the $x_i$-th from the beginning to join the laboratory leaves the laboratory.
When $t_i=3$, this is an event in which the research power of everyone in the laboratory changes by $+x_i$.
The constraints are as follows.
- All inputs are integers.
- $1 \le Q \le 10^5$
- $1 \le t_i \le 3$ $(1 \le i \le Q)$
- When $t_i=1$, $-10^9 \le x_i \le 10^9$
- When $t_i=2$, $1 \le x_i$, and the researcher who was the $x_i$-th to join is guaranteed to be in the laboratory at the time of the $i$-th event.
- When $t_i=3$, $-10^9 \le x_i \le 10^9$
Output
Output the labo-index immediately after each event, $1$ per line.
Sample
Sample 1
Input
5 1 1 1 2 1 3 1 4 1 5
Output
1 1 2 2 3
In the $1$-st event, a researcher with research power $1$ joins.
The research powers are now, in order, $1$, and the labo-index is $1$.
In the $2$-nd event, a researcher with research power $2$ joins.
The research powers are now, in order, $1, 2$, and the labo-index is $1$.
In the $3$-rd event, a researcher with research power $3$ joins.
The research powers are now, in order, $1, 2, 3$, and the labo-index is $2$.
In the $4$-th event, a researcher with research power $4$ joins.
The research powers are now, in order, $1, 2, 3, 4$, and the labo-index is $2$.
In the $5$-th event, a researcher with research power $5$ joins.
The research powers are now, in order, $1, 2, 3, 4, 5$, and the labo-index is $3$.
Sample 2
Input
4 1 1 1 2 1 3 2 2
Output
1 1 2 1
In the $1$-st event, a researcher with research power $1$ joins.
The research powers are now, in order, $1$, and the labo-index is $1$.
In the $2$-nd event, a researcher with research power $2$ joins.
The research powers are now, in order, $1, 2$, and the labo-index is $1$.
In the $3$-rd event, a researcher with research power $3$ joins.
The research powers are now, in order, $1, 2, 3$, and the labo-index is $2$.
In the $4$-th event, the researcher who was the $2$-nd to join leaves.
The research powers are now, in order, $1, 3$, and the labo-index is $1$.
Sample 3
Input
5 1 1 1 2 1 3 3 2 3 -10
Output
1 1 2 3 0
In the $1$-st event, a researcher with research power $1$ joins.
The research powers are now, in order, $1$, and the labo-index is $1$.
In the $2$-nd event, a researcher with research power $2$ joins.
The research powers are now, in order, $1, 2$, and the labo-index is $1$.
In the $3$-rd event, a researcher with research power $3$ joins.
The research powers are now, in order, $1, 2, 3$, and the labo-index is $2$.
In the $4$-th event, the research power of everyone changes by $+2$.
The research powers are now, in order, $3, 4, 5$, and the labo-index is $3$.
In the $5$-th event, the research power of everyone changes by $-10$.
The research powers are now, in order, $-7, -6, -5$, and the labo-index is $0$.
Sample 4
Input
10 1 396579765 1 798135558 1 901129114 3 -929424919 2 3 1 -643609488 3 697031258 3 -245746533 1 -804449362 2 2
Output
1 2 3 0 0 0 3 1 1 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。