No.649 ここでちょっとQK!

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 97
作問者 : kakira9618kakira9618 / テスター : matsu7874matsu7874
6 ProblemId : 2120 / 出題時の順位表

問題文

整数$Q$、$K$が与えられます。
次のクエリ($Q$個)を処理してください。

  • タイプ1: 配列$S$に数$v$を追加する
  • タイプ2: 配列$S$の要素数が$K$以上の場合、$S$の要素のうち$K$番目に小さい要素を1つ出力し、$S$から削除する。$S$の要素数が$K$未満の場合は、-1を出力する。

(※全てのタイプ2のクエリについて、$K$は共通です)

入力

$Q$ $K$
$query_1$
$query_2$
…
$query_Q$

入力は全て整数で与えられる。

$Q (1\leq Q\leq200000)$はクエリの数を表す
$K (1\leq K\leq200000)$はタイプ2のクエリにおいて、何番目に小さい数を答えれば良いかを表す。

続く$Q$行にはクエリの情報が示される。
$query_i$ は$i$番目のクエリを表す。各クエリは次のフォーマットで与えられる。

タイプ1のクエリの場合:
$1\ v_i$
タイプ2のクエリの場合:
$2$

ここで、$v_i (0\leq v_i\leq10^{18})$は$i$番目のクエリ(タイプ1)において、配列に追加する数を表す。
タイプ2のクエリは1個以上存在する。

入力・出力行数が多いので、IOには気をつけてください! 特にLL系の言語の場合は、制約がタイトなため注意してください!

出力

タイプ2のクエリによる結果を改行区切りで出力せよ。最後に改行すること。

サンプル

サンプル1
入力
15 3
1 3
1 4
1 5
2
2
1 10
1 10
1 1
2
1 3
2
1 1000
2
1 0
2
出力
5
-1
4
3
10
3

配列$S$は次のように変化します。

  • 1番目~3番目のクエリ: $S = \{3, 4, 5\}$
  • 4番目のクエリ: 5を出力、$S = \{3, 4\}$
  • 5番目のクエリ: -1を出力、$S = \{3, 4\}$
  • 6番目~8番目のクエリ: $S = \{1, 3, 4, 10, 10\}$
  • 9番目のクエリ: 4を出力、$S = \{1, 3, 10, 10\}$
  • 10番目のクエリ: $S = \{1, 3, 3, 10, 10\}$
  • 11番目のクエリ: 3を出力、$S = \{1, 3, 10, 10\}$
  • 12番目のクエリ: $S = \{1, 3, 10, 10, 1000\}$
  • 13番目のクエリ: 10を出力、$S = \{1, 3, 10, 1000\}$
  • 14番目のクエリ: $S = \{0, 1, 3, 10, 1000\}$
  • 15番目のクエリ: 3を出力、$S = \{0, 1, 10, 1000\}$
サンプル2
入力
4 1
1 10
1 10
2
2
出力
10
10

クエリによって、配列$S$の要素は重複することがあります。
重複している場合でも、タイプ2のクエリで削除される要素が1つであることに気をつけてください。

サンプル3
入力
4 2
1 9
1 10000000000000000
1 90000000000000000
2
出力
10000000000000000

大きい数が入力される場合があります。9と京と9京なので2番目に小さい京を出力します。

サンプル4
入力
1 1
2
出力
-1

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。