問題一覧 > 通常問題

No.3198 Monotonic Query

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 134
作問者 : YY-otter / テスター : Nauclhlt🪷
ProblemId : 12431 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-07-05 08:14:55

問題文

あなたは最初、空の数列 $A$ を持っています。$Q$ 個のクエリを順番に処理してください。クエリには2種類あります。

  • クエリ1: 1 x …… 数列 $A$ の末尾に整数 $x$ を追加する。
  • クエリ2: 2 k …… 現在の数列 $A$ のうち、末尾から $k$ 個の要素の中で、値が最も大きいものを出力する。
ただし、クエリ2 ( $2\ k$ ) が与えられるとき、現在の数列 $A$ の要素数は $k$ 以上であることが保証されます。

入力

$Q$
$query_1$
$\dots$
$query_Q$

  • $query_i$ は " $1\ x_i$ " または " $2\ k_i$ "
  • $1\leq Q\leq 2\times 10^5$
  • $1\leq x_i\leq 10^9$
  • $1\leq k_i\leq($ 現在の $|A|)$

出力

クエリ2が与えられるたびに、結果を改行区切りで出力してください。
最後に改行してください。

サンプル

サンプル1
入力
8
1 10
1 30
1 20
2 2
1 50
2 3
1 40
2 4
出力
30
50
50
  1. 1 10: $A = (10)$
  2. 1 30: $A = (10, 30)$
  3. 1 20: $A = (10, 30, 20)$
  4. 2 2: $A$ の末尾2要素 $(30, 20)$ の最大値は $30$
  5. 1 50: $A = (10, 30, 20, 50)$
  6. 2 3: $A$ の末尾3要素 $(30, 20, 50)$ の最大値は $50$
  7. 1 40: $A = (10, 30, 20, 50, 40)$
  8. 2 4: $A$ の末尾4要素 $(30, 20, 50, 40)$ の最大値は $50$
サンプル2
入力
10
1 3
2 1
1 4
2 1
1 5
1 9
2 2
1 6
2 5
2 3
出力
3
4
9
9
9

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