← 返回题目列表

AtCoder · joi2018_yo_f

F. Lth K 个数字 (LthKthNumber)

中文机器翻译题面 查看原题

配点: 100 点

問題文

并排放置在一排 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 找到你的分数。

制約

  • 1 ≦ N ≦ 200000
  • 1 ≦ K ≦ N
  • 1 ≦ a_i ≦ N
  • 1 ≦ L
  • JOI 您写入的整数是 L 或更多。

入力

输入是按以下格式从标准输入给出的。

N K L
a_1 a_2 ... a_N

出力

JOI 你的分数 1 输出在一行。

小課題 1 [6点]

  • N ≦ 100

小課題 2 [33点]

  • N ≦ 4000

小課題 3 [61点]

  • 没有其他限制。

入力例 1

4 3 2
4 3 1 2

出力例 1

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 。注意,如果有多个相同的整数,则会被计算两次。


入力例 2

5 3 3
1 5 2 2 4

出力例 2

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 。从


入力例 3

6 2 9
1 5 3 4 2 4

出力例 3

4

入力例 4

6 2 8
1 5 3 4 2 4

出力例 4

3