L番目のK番目の数 (LthKthNumber)
日本語
Language
Contribute a translation- Time limit
- 2000 ms
- Memory limit
- 256 MB
- Submissions
- 0
- Correct
- 0
- Solved by
- 0
- AC rate
- —
Statement
横一列に並べられた \(N\) 枚のカードがある．左から \(i\) 枚目(\(1 ≦ i ≦ N\))のカードには，整数 \(a_i\) が書かれている．
JOI 君は，これらのカードを用いて次のようなゲームを行う．連続する \(K\) 枚以上のカードの列を選び，次の操作を行う．
- 選んだカードを，書かれている整数が小さい順に左から並べる．
- 並べたカードのうち，左から \(K\) 番目のカードに書かれた整数を紙に書き出す．
- 選んだカードを，すべて元の位置に戻す．
この操作を，連続する \(K\) 枚以上のカードの列すべてに対して行う．すなわち，\(1 ≦ l ≦ r ≦ N\) かつ \(K ≦ r - l + 1\) を満たすすべての \((l,r)\) について，\(a_l, a_{l+1}, ..., a_r\) のうち \(K\) 番目に小さな整数を書き出す．
こうして書き出された整数を，左から小さい順に並べる．並べた整数のうち，左から \(L\) 番目のものがこのゲームにおける JOI 君の得点である．JOI 君の得点を求めよ．
Constraints
- \(1 ≦ N ≦ 200000\)
- \(1 ≦ K ≦ N\)
- \(1 ≦ a_i ≦ N\)
- \(1 ≦ L\)
- JOI 君が書き出す整数は \(L\) 個以上である．
Input
入力は以下の形式で標準入力から与えられる．
\(N\) \(K\) \(L\)
\(a_1\) \(a_2\) \(...\) \(a_N\)
Output
JOI 君の得点を \(1\) 行で出力せよ．
Subtasks
小課題 1 [6点]
- \(N ≦ 100\)
小課題 2 [33点]
- \(N ≦ 4000\)
小課題 3 [61点]
- 追加の制限はない．
Examples
4 3 2 4 3 1 2
3
\(1 ≦ l ≦ r ≦ N (= 4)\) かつ \(K (= 3) ≦ r - l + 1\) を満たす \((l,r)\) は，\((1,3), (1,4), (2,4)\) の \(3\) 通りある．
これらの \((l,r)\) に対し，\(a_l, a_{l+1}, ..., a_r\) で \(3\) 番目に小さな整数は，それぞれ \(4, 3, 3\) である．
このうち \(L (= 2)\) 番目に小さい整数は \(3\) なので，JOI 君の得点は \(3\) である．同じ整数が複数あるときも，重複して数えることに注意せよ．
5 3 3 1 5 2 2 4
4
JOI 君が書き出す整数は，
- \((l,r) = (1,3)\) に対し \(5\)
- \((l,r) = (1,4)\) に対し \(2\)
- \((l,r) = (1,5)\) に対し \(2\)
- \((l,r) = (2,4)\) に対し \(5\)
- \((l,r) = (2,5)\) に対し \(4\)
- \((l,r) = (3,5)\) に対し \(4\)
である．このうち \(L (= 3)\) 番目に小さい整数は \(4\) である．
6 2 9 1 5 3 4 2 4
4
6 2 8 1 5 3 4 2 4
3
Notes
JOI 2018 · JCIOI · CC BY-SA 4.0
Tags
No tags yet