No.3198 Monotonic Query
レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 134
作問者 :
YY-otter
/ テスター :
Nauclhlt🪷
タグ : / 解いたユーザー数 134
作問者 :

問題文最終更新日: 2025-07-05 08:14:55
問題文
あなたは最初、空の数列 $A$ を持っています。$Q$ 個のクエリを順番に処理してください。クエリには2種類あります。
- クエリ1:
1 x
…… 数列 $A$ の末尾に整数 $x$ を追加する。 - クエリ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 10
: $A = (10)$1 30
: $A = (10, 30)$1 20
: $A = (10, 30, 20)$2 2
: $A$ の末尾2要素 $(30, 20)$ の最大値は $30$1 50
: $A = (10, 30, 20, 50)$2 3
: $A$ の末尾3要素 $(30, 20, 50)$ の最大値は $50$1 40
: $A = (10, 30, 20, 50, 40)$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もしくは右上の雲マークをクリックしてアカウントを作成してください。