問題一覧 > 通常問題

No.1921 Range LthKth Query

レベル : / AI推定難易度 : 2575 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 7
作問者 : tatyam
お気に入りにしたユーザー ProblemId : 8080 / 自分の提出
問題文最終更新日: 2022-05-01 23:51:17
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

You are given an integer sequence $A = (A_1, A_2, \dots, A_N)$ of $N$ elements and integers $K, L$.

You are given $Q$ queries of the following form. Find the answer to each of them.

  • Integers $l, r$ are given. Find the $L$-th $K$-th number of the integer sequence $B = (A_l, A_{l + 1}, \dots, A_r)$.

Input

The input is given from Standard Input in the following format.

$N$ $K$ $L$  
$A_1$ $A_2$ $\cdots$ $A_N$  
$Q$  
$\text{Query}_1$  
$\text{Query}_2$  
$\vdots$  
$\text{Query}_Q$ 

Here, $\text{Query}_i$ ($1≤i≤Q$) represents the $i$-th query. Each query is given in the following format.

$l$ $r$
  • All input values are integers.
  • $1≤N≤2.5\times 10^3$
  • $1≤K≤N$
  • $1≤L$
  • $1≤A_i≤N$ ($1≤i≤N$)
  • $1≤Q≤2.5\times 10^5$
  • For each query, $1≤l≤r≤N,\ \ r - l + 1≥K,\ \ L≤\frac{(r-l-K+2)(r-l-K+3)}{2}$

Additionally, there is an evil case with $N = 5000$. This test case does not affect the submission result.

Output

Print $Q$ lines. On the $i$-th line ($1≤i≤Q$), print the answer to the $i$-th query.

Sample

Sample 1
Input
4 3 2
3 1 2 4
1
1 4
Output
3

The contiguous subarrays of $(3, 1, 2, 4)$ with length at least $K (= 3)$ are the following $3$: $(3, 1, 2), (1, 2, 4), (3, 1, 2, 4)$. Their $K$-th numbers are $3, 4, 3$ respectively, and the $L (= 2)$-th number among these is $3$.

Sample 2
Input
4 3 1
3 1 2 4
3
1 3
2 4
1 4
Output
3
4
3
Sample 3
Input
15 4 6
8 5 6 6 2 1 14 8 9 3 5 4 2 1 7
12
1 6
4 15
7 15
5 13
3 13
3 8
6 11
6 13
2 12
3 11
8 14
1 7
Output
8
3
4
5
4
14
14
5
5
6
5
6

Source

CPCTF22

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。