#2940. 疫苗与病毒

疫苗与病毒

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

2022 年 13 月 35 日,磕学家们终于找到了克制鑫棺病毒的法宝——鑫棺疫苗。

这种疫苗的用法非常神奇。每一次,它只能消灭一个病毒。但是,由于鑫棺病毒具有的特殊性质,每一个病毒具有一个连接度。

现在,磕学家们找到了求连接度最大的病毒的方法。具体来说,就是将 nn 个病毒排成一排,每个病毒有一个危害值,然后取所有长度 m≥m 的区间,将危害值第 mm 大的病毒放入另一堆。接着,在挑出来的这一堆中选择危害值第 kk 小的病毒,就是连接度最大的病毒。

磕学家们想让你求出这个病毒的危害值。

输入格式

第一行三个整数 n,m,kn,m,k

第二行 nn 个整数,表示病毒的危害值 aia_i

输出格式

输出一行表示答案。

样例输入 1

5 3 5
5 2 4 3 1

样例输出 1

3

样例解释

合法的区间有 {5,2,4},{2,4,3},{4,3,1},{5,2,4,3},{2,4,3,1},{5,2,4,3,1}\{5,2,4\},\{2,4,3\},\{4,3,1\},\{5,2,4,3\},\{2,4,3,1\},\{5,2,4,3,1\},挑出各个区间第三大的数,并排好序后为 {1,2,2,2,3,3}\{1,2,2,2,3,3\},第五小的是 33

数据范围

下表数据表示最大值。

Subtask n m 特殊性质 分值
1 20 20
2 1000 保证 k=1 10
3 10410^4 1
4 10610^6 60

对于所有的数据,1mn106,1ai1091≤m≤n≤10^6,1≤a_i≤10^9

第二届小云雀杯提高组

未参加
状态
已结束
规则
OI
题目
4
开始于
2023-4-23 19:30
结束于
2023-4-23 22:18
持续时间
2.8 小时
主持人
参赛人数
210