連続部分列
(paizaランク S 相当)
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
シェア用URL:
ツイートする
問題
下記の問題をプログラミングしてみよう！
長さ N の数列 A = (A_1, A_2, ..., A_N) が与えられます。
数列 A の連続部分列 (A_L, A_{L + 1}, ..., A_R) について、その最小値 min(A_L, A_{L + 1}, ..., A_R) を min(A, L, R) と表すことにします。
すべての L, R (1 ≦ L ≦ R ≦ N) に対する min(A, L, R) を昇順（小さい順）に並べてできる長さ N × (N + 1) / 2 の数列の K 番目の要素を求めてください。
- 入力される値
-
N K
A_1 A_2 ... A_N
・ 1 行目に、数列の長さ N と 整数 K が与えられます。
・ 2 行目に、数列 A の各要素 A_i が半角スペース区切りで与えられます。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
問題の答えを、1 行に整数で出力してください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 入力はすべて整数
・ 1 ≦ N ≦ 300,000 = 3 × 10^5
・ 1 ≦ K ≦ N × (N + 1) / 2
・ 1 ≦ A_i ≦ 1,000,000,000 = 10^9
- 入力例1
-
3 3
1 3 4
- 出力例1
-
1
