No.618 labo-index

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 37
作問者 :

n_knuu / テスター :

夕叢霧香(ゆうむらきりか)

2 ProblemId : 2024 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2017-11-27 04:40:32

あらすじ

(この部分は読み飛ばしても問題ありません)
あなたは研究の道を究め、自分の研究室を開くことが出来るようになりました。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$ される

各イベントが起こった直後の labo-index を全て出力して下さい。

入力

Q
t_1 x_1
t_2 x_2
:
t_Q x_Q

$t_{i}$ は $i$ $(1 \leq i \leq Q)$ 番目のイベントの種類を表します。
$t_{i} = 1$ のとき、これは研究室に研究力 $x_{i}$ の研究者が入ってくるイベントです。
$t_{i} = 2$ のとき、これは最初から $x_{i}$ 番目に研究室に参加した研究者が研究室から出ていくイベントです。
$t_{i} = 3$ のとき、これは研究室全員の研究力が $+ x_{i}$ されるイベントです。

制約は以下の通りです。

入力は全て整数である
$1 \leq Q \leq 10^{5}$
$1 \leq t_{i} \leq 3$ $(1 \leq i \leq Q)$
$t_{i} = 1$ のとき $- 10^{9} \leq x_{i} \leq 10^{9}$
$t_{i} = 2$ のとき $1 \leq x_{i}$ であり、かつ $x_{i}$ 番目に参加した研究者は $i$ 番目のイベントの時点で必ず研究室にいるものとする
$t_{i} = 3$ のとき $- 10^{9} \leq x_{i} \leq 10^{9}$

出力

各イベントが発生した直後のlabo-index を $1$ 行ずつ出力してください。

サンプル

サンプル1

入力

出力

$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

入力

出力

$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

入力

出力

$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

出力

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。