C - データ構造
解説
/
実行時間制限: 2 sec / メモリ制限: 256 MB
問題文
数の集合 S に対する以下のクエリを処理してください。
- タイプ 1 : S に数 X を追加する。
- タイプ 2 : S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する。
入力
入力は以下の形式で標準入力から与えられる。
Q T_1 X_1 T_2 X_2 : T_Q X_Q
- 1 行目には、クエリの個数を表す整数 Q (1 ≦ Q ≦ 200,000) が与えられる。
-
2 行目からの Q 行には、クエリの情報が与えられる。このうち i 行目では、2 つの整数 T_i (1 ≦ T_i ≦ 2), X_i (1 ≦ X_i ≦ 200,000) が空白区切りで与えられる。これは、
- T_i = 1 の場合、「S に数 X_i を追加する」というクエリを表す。ただし、クエリを処理する前の S には X_i が含まれていないことが保証される。
- T_i = 2 の場合、「S に含まれる数のうち X_i 番目に小さい数を答え、その数を S から削除する」というクエリを表す。ただし、クエリを処理する前の S に含まれる数の個数が X_i 個以上であることが保証される。
出力
タイプ 2 のクエリの個数を Q_2 とすると、出力は Q_2 行からなる。このうち i 行目には、タイプ 2 のクエリのうち i 番目のものに対する答えを出力せよ。出力の末尾にも改行を入れること。
入力例1
5 1 11 1 29 1 89 2 2 2 2
出力例1
29 89
入力例2
12 1 8932 1 183450 1 34323 1 81486 1 127874 1 114850 1 55277 1 112706 2 3 1 39456 1 52403 2 4
出力例2
55277 52403