No.1921 Range LthKth Query
タグ : / 解いたユーザー数 7
作問者 :
tatyam
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もしくは右上の雲マークをクリックしてアカウントを作成してください。