問題一覧 > 通常問題

No.1921 Range LthKth Query

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 5
作問者 : tatyamtatyam
2 ProblemId : 8080 / 自分の提出
問題文最終更新日: 2022-05-01 23:51:17

問題文

$N$ 要素の整数列 $A = (A_1, A_2, \dots, A_N)$ と、整数 $K, L$ が与えられます。

以下の形式のクエリが $Q$ 個与えられるので、それぞれについて答えを求めてください。

入力

入力は以下の形式で標準入力から与えられる。

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

ただし、$\text{Query}_i$ ($1≤i≤Q$) は $i$ 個目のクエリを表す。各クエリは以下の形式で与えられる。

$l$ $r$
  • 入力は全て整数
  • $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$
  • 各クエリについて、$1≤l≤r≤N,\ \ r - l + 1≥K,\ \ L≤\frac{(r-l-K+2)(r-l-K+3)}{2}$

また、$N = 5000$ の evil ケースが存在する。このテストケースは提出結果には影響しない。

出力

$Q$ 行出力せよ。$i$ 行目 ($1≤i≤Q$) には $i$ 個目のクエリに対する答えを出力せよ。

サンプル

サンプル1
入力
4 3 2
3 1 2 4
1
1 4
出力
3

$(3, 1, 2, 4)$ の長さ $K (= 3)$ 以上の連続部分列は $(3, 1, 2), (1, 2, 4), (3, 1, 2, 4)$ の $3$ 個です。これらの $K$ 番目の数はそれぞれ $3, 4, 3$ で、この中の $L (= 2)$ 番目の数は $3$ です。

サンプル2
入力
4 3 1
3 1 2 4
3
1 3
2 4
1 4
出力
3
4
3
サンプル3
入力
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
出力
8
3
4
5
4
14
14
5
5
6
5
6

出典

CPCTF22

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