No.618 labo-index
タグ : / 解いたユーザー数 36
作問者 :
n_knuu
/ テスター :
夕叢霧香(ゆうむらきりか)
あらすじ
(この部分は読み飛ばしても問題ありません)あなたは研究の道を究め、自分の研究室を開くことが出来るようになりました。Congratulations!
研究室を運営していく中では、新たに研究員が入ってきたり、また、出ていったりすることもでしょう。
また、研究資金の獲得により研究室全体の士気が上がったり、不祥事により落ち込んだりすることもあるでしょう。
そこでまずあなたは、研究室の運営について、様々な場合をシミュレーションしてみることにしました。
問題文
研究者の研究力という数値がある整数で表されるとします。
このとき、研究室の labo-index $L$ は、以下の条件を満たす $l$ のうち最大の非負整数とします。
条件: 研究力が $l$ 以上である研究者が研究室に $l$ 人以上いる
例えば $5$ 人の研究者がいる研究室において、それぞれの研究者の研究力が $1, 2, 3, 4, 5$ である場合、この研究室の labo-index は $L=3$ となります。
また、研究室に研究者が誰もいない場合の labo-index は $L=0$ であるとします。
まず最初、研究室には $0$ 人の研究者がいるとします。
このとき、$Q$ 回の以下の3ついずれかのイベントが順に発生します。
- 研究室に研究力 $x$ の研究者が入ってくる
- 最初から $x$ 番目に研究室に参加した研究者が研究室から出ていく
- 研究室全員の研究力が $+x$ される
入力
Q t_1 x_1 t_2 x_2 : t_Q x_Q
$t_i$ は $i$ $(1 \le i \le Q)$ 番目のイベントの種類を表します。
$t_i=1$ のとき、これは研究室に研究力 $x_i$ の研究者が入ってくるイベントです。
$t_i=2$ のとき、これは最初から $x_i$ 番目に研究室に参加した研究者が研究室から出ていくイベントです。
$t_i=3$ のとき、これは研究室全員の研究力が $+x_i$ されるイベントです。
制約は以下の通りです。
- 入力は全て整数である
- $1 \le Q \le 10^5$
- $1 \le t_i \le 3$ $(1 \le i \le Q)$
- $t_i=1$ のとき $-10^9 \le x_i \le 10^9$
- $t_i=2$ のとき $1 \le x_i$ であり、かつ $x_i$ 番目に参加した研究者は $i$ 番目のイベントの時点で必ず研究室にいるものとする
- $t_i=3$ のとき $-10^9 \le x_i \le 10^9$
出力
各イベントが発生した直後のlabo-index を $1$ 行ずつ出力してください。
サンプル
サンプル1
入力
5 1 1 1 2 1 3 1 4 1 5
出力
1 1 2 2 3
$1$ 番目のイベントでは、研究力 $1$ の研究者が入ってきます。
このとき研究力は順に $1$ であり、labo-index は $1$ です。
$2$ 番目のイベントでは、研究力 $2$ の研究者が入ってきます。
このとき研究力は順に $1, 2$ であり、labo-index は $1$ です。
$3$ 番目のイベントでは、研究力 $3$ の研究者が入ってきます。
このとき研究力は順に $1, 2, 3$ であり、labo-index は $2$ です。
$4$ 番目のイベントでは、研究力 $4$ の研究者が入ってきます。
このとき研究力は順に $1, 2, 3, 4$ であり、labo-index は $2$ です。
$5$ 番目のイベントでは、研究力 $5$ の研究者が入ってきます。
このとき研究力は順に $1, 2, 3, 4, 5$ であり、labo-index は $3$ です。
サンプル2
入力
4 1 1 1 2 1 3 2 2
出力
1 1 2 1
$1$ 番目のイベントでは、研究力 $1$ の研究者が入ってきます。
このとき研究力は順に $1$ であり、labo-index は $1$ です。
$2$ 番目のイベントでは、研究力 $2$ の研究者が入ってきます。
このとき研究力は順に $1, 2$ であり、labo-index は $1$ です。
$3$ 番目のイベントでは、研究力 $3$ の研究者が入ってきます。
このとき研究力は順に $1, 2, 3$ であり、labo-index は $2$ です。
$4$ 番目のイベントでは、$2$ 番目に入ってきた研究者が出ていきます。
このとき研究力は順に $1, 3$ であり、labo-index は $1$ です。
サンプル3
入力
5 1 1 1 2 1 3 3 2 3 -10
出力
1 1 2 3 0
$1$ 番目のイベントでは、研究力 $1$ の研究者が入ってきます。
このとき研究力は順に $1$ であり、labo-index は $1$ です。
$2$ 番目のイベントでは、研究力 $2$ の研究者が入ってきます。
このとき研究力は順に $1, 2$ であり、labo-index は $1$ です。
$3$ 番目のイベントでは、研究力 $3$ の研究者が入ってきます。
このとき研究力は順に $1, 2, 3$ であり、labo-index は $2$ です。
$4$ 番目のイベントでは、全員の研究力が $+2$ されます。
このとき研究力は順に $3, 4, 5$ であり、labo-index は $3$ です。
$5$ 番目のイベントでは、全員の研究力が $-10$ されます。
このとき研究力は順に $-7, -6, -5$ であり、labo-index は $0$ です。
サンプル4
入力
10 1 396579765 1 798135558 1 901129114 3 -929424919 2 3 1 -643609488 3 697031258 3 -245746533 1 -804449362 2 2
出力
1 2 3 0 0 0 3 1 1 0
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。