F - Hotel
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
長さ 1 の整数列 A=(1) があります。 クエリが Q 個与えられるので順に処理してください。
クエリは以下の 3 種類です。
いずれも、各クエリ処理前の数列 A の長さを n とし、A=(a_{1},a_{2},\dots,a_{n}) とします。
1 x
: A を長さ n+1 の数列 (x,a_{1},a_{2},\dots,a_{n}) に置き換える。2 x
: A を長さ 2n の数列 (x,a_{1},x,a_{2},\dots,x,a_{n}) に置き換える。3 x
: x>n ならば -1 を出力する。 x\le n ならば a_{x} を出力する。
制約
- 1 \leq Q \leq 2\times 10^5
- 1\leq x\leq 10^{9}
- 出力クエリが少なくとも1つ存在する
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
Q t_1 x_1 t_2 x_2 \vdots t_Q x_Q
ここで、t_i (1\leq i\leq Q) はクエリの種類を表す整数で、t_i=1,2,3 のいずれかである。
出力
t_i=3 を満たすクエリの回数を q として、q 行出力せよ。 j (1\leq j\leq q) 行目では、j 番目のそのようなクエリに対する答えを出力せよ。
入力例 1
6 1 4 3 3 1 3 3 2 2 3 3 2
出力例 1
-1 4 3
クエリ 1 前: A=(1)
クエリ 1 後: A=(4,1)
クエリ 2 後: A=(4,1)
クエリ 3 後: A=(3,4,1)
クエリ 4 後: A=(3,4,1)
クエリ 5 後: A=(3,3,3,4,3,1)
クエリ 6 後: A=(3,3,3,4,3,1)
となっています。
入力例 2
8 1 8 2 5 2 5 3 7 3 8 3 9 2 3 3 1
出力例 2
5 1 -1 3