Problem:


Score : 600 points

Problem Statement

You are given an integer sequence A of length N and an integer K.
You will perform the following operation on this sequence Q times:

Choose a contiguous subsequence of length K, then remove the smallest element among the K elements contained in the chosen subsequence (if there are multiple such elements, choose one of them as you like).

Let X and Y be the values of the largest and smallest element removed in the Q operations. You would like X-Y to be as small as possible.
Find the smallest possible value of X-Y when the Q operations are performed optimally.

Constraints

1 \leq N \leq 2000

1 \leq K \leq N

1 \leq Q \leq N-K+1

1 \leq A_i \leq 10^9

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K Q
A_1 A_2 ... A_N

Output

Print the smallest possible value of X-Y.

Sample Input 1

5 3 2
4 3 1 5 2

Sample Output 1

1

In the first operation, whichever contiguous subsequence of length 3 we choose, the minimum element in it is 1.
Thus, the first operation removes A_3=1 and now we have A=(4,3,5,2).
In the second operation, it is optimal to choose (A_2,A_3,A_4)=(3,5,2) as the contiguous subsequence of length 3 and remove A_4=2.
In this case, the largest element removed is 2, and the smallest is 1, so their difference is 2-1=1.

Sample Input 2

10 1 6
1 1 2 3 5 8 13 21 34 55

Sample Output 2

7

Sample Input 3

11 7 5
24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784

Sample Output 3

451211184



Sample input:
5 3 2
4 3 1 5 2


Sample output:
1

Submission status: Accepted

Solution code:
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
D = set()
for i in range(N):
    D.add(A[i])

D = list(D)
ans = float('inf')
for Y in D:
    T = []
    tmp = []
    for j in range(N):
        if A[j] >= Y:
            tmp.append(A[j])
        else:
            if len(tmp) >= K:
                tmp = sorted(tmp)
                T += tmp[:len(tmp) - K + 1]
            tmp = []

    if len(tmp) >= K:
        tmp = sorted(tmp)
        T += tmp[:len(tmp) - K + 1]

    if len(T) >= Q:
        T = sorted(T)
        T = T[:Q]
        ans = min(ans, T[-1] - T[0])

print(ans)

Submission status: Accepted

Solution code:
n, k, q = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]

#print(a)
ans = float("inf")
for i in range(n):
    y = a[i]

    c = []
    c_k = []
    for j in range(n):
        if a[j] >= y:
            c_k.append(a[j])
        else:
            c.append(c_k)
            c_k = []
    else:
        c.append(c_k)

    d = []
    for j in c:
        if len(j) >= k:
            j.sort()
            for l in range(len(j)-k+1):
                d.append(j[l])

    if len(d) >= q:
        d.sort()
        ans = min(ans, d[q-1] - d[0])

print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')

N, K, Q = map(int, input().split())
a = tuple(map(int, input().split()))

ans = inf
for ma in sorted(set(a)):
    res = []
    seq = 0
    for i, aa in enumerate(a):
        if aa >= ma:
            # 最小値以上の要素は部分列に含めてよい
            seq += 1
        else:
            # 最小値未満の要素が来たら、
            # それまでの部分列を処理する
            if seq >= K:
                res.extend(sorted(a[i - seq:i])[:seq - K + 1])
            seq = 0
    if seq >= K:
        res.extend(list(sorted(a[-seq:]))[:seq - K + 1])
    seq = 0
    if len(res) < Q: continue
    res.sort()
    ans = min(ans, res[Q - 1] - ma)
print(ans)

Submission status: Accepted

Solution code:
inf = float('inf')

N, K, Q = map(int, input().split())
a = tuple(map(int, input().split()))

ans = inf
for ma in sorted(set(a)):
    res = []
    seq = 0
    for i in range(N):
        if a[i] >= ma:
            # 最小値以上の要素は部分列に含めてよい
            seq += 1
        else:
            # 最小値未満の要素が来たら、
            # それまでの部分列を処理する
            if seq >= K:
                res.extend(sorted(a[i - seq:i])[:seq - K + 1])
            seq = 0
    if seq >= K:
        res.extend(list(sorted(a[-seq:]))[:seq - K + 1])
    seq = 0
    if len(res) < Q: continue
    res.sort()
    ans = min(ans, res[Q - 1] - ma)
print(ans)

Submission status: Accepted

Solution code:
n, k, q = map(int, input().split())
alist = list(map(int, input().split()))
ans = None
if q == 1:
  print(0)
else:
  for i, a in enumerate(alist):
    spla = []
    preva = -1
    ailist = alist[:i] + alist[i+1:]
    for j, _a in enumerate(ailist):
      if _a < a:
        spla.append(ailist[preva+1:j])
        preva = j
    if not preva == len(ailist)-1:
      spla.append(ailist[preva+1:])
    conda = []
    for sa in spla:
      if len(sa) >= k:
        conda.extend(list(sorted(sa))[:len(sa)-k+1])
    if len(conda) < q-1:
      continue
    else:
      y = list(sorted(conda))[q-2]
      if ans is None or ans > y - a:
        ans = y - a

  print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc098/submissions/2581691
inf = float('inf')


def calc_max_a(min_a):
    cands = []  # 候補
    seq = 0
    for i, aa in enumerate(a):
        if aa < min_a:
            if seq >= K:
                cands.extend(sorted(a[i - seq:i])[:seq - K + 1])
            seq = 0
        else:
            seq += 1
    if seq >= K:
        cands.extend(sorted(a[- seq:])[:seq - K + 1])

    if len(cands) < Q:
        return -1  # Query回数の操作ができない
    else:
        return sorted(cands)[Q - 1]  # Q回目の操作で取り出す値


N, K, Q = map(int, input().split())
a = tuple(map(int, input().split()))

ans = inf
for min_a in sorted(set(a)):
    max_a = calc_max_a(min_a)
    if max_a < 0: break  # min_a以上の値を最小値にするような操作は存在しない
    ans = min(ans, max_a - min_a)
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys, collections, bisect, math, itertools, heapq
from fractions import gcd 
#input = sys.stdin.readline #文字列入力のときは注意

n,k,q = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
aa = sorted(a)
a += [0]

ans = 10**9+1
mmm = 0
for i,m in enumerate(aa):
#    print(i,m)
    if mmm == m: continue
    hh = [] 
    mae = 0
    for j,aj in enumerate(a):
        if aj < m:
            h=a[mae:j]
#            print(h,"h",j,mae)
            heapq.heapify(h)
            for _ in range(j-mae-k+1):
                hh.append(heapq.heappop(h))
            mae = j+1
    mmm = m
    
#    print("hh",hh)
    if len(hh) < q: break
    else:
        hh.sort()
        ans = min(ans, hh[q-1]-hh[0])
            
print(ans)

Submission status: Accepted

Solution code:
N, K, Q = map(int, input().split())
A = [int(a) for a in input().split()]

minSub = 10**10
for a in A:
    start = False
    end = 0
    subarray, newarray = [], []
    for i in range(N):
        if A[i] >= a:
            newarray.append(A[i])
            start = True
        else:
            if start:
                start = False
                if len(newarray) >= K:
                    newarray.sort()
                    for j in range(len(newarray) - K + 1):
                        subarray.append(newarray[j])
                newarray = []
    if len(newarray) >= K:
        newarray.sort()
        for j in range(len(newarray) - K + 1):
            subarray.append(newarray[j])
    if len(subarray) >= Q: 
        subarray.sort()
        minSub = min(minSub, subarray[Q-1] - a)
print(minSub)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def solve(n, k, q, a):

    sorted_pairs = [(ai, i) for i, ai in enumerate(a)]
    sorted_pairs.sort()


    ans = 10 ** 10
    segments = [(0, n)]
    ly = 0
    for i in range(n - q + 1):
        y, _ = sorted_pairs[i]
        if y == ly:
            continue
        ly = y
        b = []
        for left, right in segments:
            if k <= right - left:
                c = a[left:right].copy()
                c.sort()
                b += c[:right - left - k + 1]
        if q <= len(b):
            b.sort()
            x = b[q - 1]
            ans = min(ans, x - y)
        i_end = n - q + 1
        for i2 in range(i + 1, n - q + 1):
            if sorted_pairs[i2][0] != y:
                i_end = i2
                break
        for i2 in range(i, i_end):
            _, j = sorted_pairs[i2]
            for h, seg in enumerate(segments):
                left, right = seg
                if left <= j and j < right:
                    segments.pop(h)
                    segments.append((left, j))
                    segments.append((j + 1, right))
                    break

    return ans


def main():
    n, k, q = input().split()
    n = int(n)
    k = int(k)
    q = int(q)
    a = list(map(int, input().split()))

    print(solve(n, k, q, a))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,K,Q=map(int,input().split())
A=[int(i) for i in input().split()]
ans=float("inf")
for i in range(N):
  l=A[i]
  A_str=" ".join([(str(a) if a>=l else "x") for a in A])
  S=[list(map(int,a.split())) for a in A_str.split("x")]
  C=[]
  for s in S:
    if len(s)>=K:
      s.sort()
      for i in range(len(s)-K+1):
        C.append(s[i])
  C.sort()
  if len(C)>=Q:
    ans=min(ans,C[Q-1]-C[0])
print(ans)

Submission status: Accepted

Solution code:
import bisect
N, K, Q = [int(i) for i in input().split()]
A = [(int(v),i) for i,v in enumerate(input().split())]
A.sort()
B = [0]*(N)
for i in range(N):
    B[A[i][1]] = i
C = [A[B[i]][0] for i in range(N)]
Candi = set(range(N))
ctr = 0
ans = []
rng = [-1,N]
while len(Candi) >= Q:
    T = sorted(Candi)
    ans.append((list(T)[0],list(T)[Q-1]))
    x = B.index(ctr)
    st = bisect.bisect_left(rng, x)
    Candi = Candi - set(sorted(B[rng[st-1]+1:x]+[2002],reverse = 1)[:K])\
    - set(sorted(B[x:rng[st]]+[2002],reverse = 1)[:K])- set([B[x]])
    bisect.insort_left(rng, x)
    ctr += 1
print(min([A[j][0]-A[i][0] for i,j in ans]))

Submission status: Accepted

Solution code:
N,K,Q = a = map(int,input().split())
a = list(map(int,input().split()))
inf = 10**10
ans = inf
for i in range(N):
    small = a[i]
    seq = []
    seqq = []
    for j in range(N):
        if a[j] < small:
            seq.append(seqq)
            seqq = []
        else:
            seqq.append(a[j])
    seq.append(seqq)
    aaa = []
    for s in seq:
        if len(s)>=K:
            s.sort()
            aaa += s[:len(s)-K+1]
    if len(aaa)>=Q:
        aaa.sort()
        ans = min(ans,aaa[Q-1]-aaa[0])
print(ans)

Submission status: Accepted

Solution code:
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
def list_split(arr, x):
    ret = []
    d = []
    for v in arr:
        if v >= x:
            d.append(v)
        elif d:
            ret.append(d)
            d = []
    else:
        if d:
            ret.append(d)
    return ret

ans = 10 ** 9
for x in sorted(A):
    y = []
    for arr in list_split(A, x):
        la = len(arr)
        if la >= K:
            y += sorted(arr)[:min(la - K + 1, Q)]
    if len(y) >= Q:
        ans = min(ans, sorted(y)[Q - 1] - x)

print(ans)

Submission status: Accepted

Solution code:
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))
ans = float("inf")
for i in range(N):
    tmp = []
    rec = []
    for j in range(N):
        if a[i] <= a[j]:
            tmp.append(a[j])
        else:
            if len(tmp) >= K:
                tmp = sorted(tmp)
                rec += tmp[:len(tmp) - K + 1]
            tmp = []

    if len(tmp) >= K:
        tmp = sorted(tmp)
        rec += tmp[:len(tmp) - K + 1]
    if Q <= len(rec):
        rec = sorted(rec)
        ans = min(ans, rec[Q - 1] - rec[0])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))
A_sorted = sorted(A)
ans = float("inf")
ap = 0
for i, a in enumerate(A_sorted):
    if a==ap:
        continue
    ap = a
    L = [0]
    d = defaultdict(list)
    for aa in A:
        if aa < a:
            if L[-1]==0:
                continue
            else:
                L.append(0)
        else:
            L[-1]+=1
            d[aa].append(len(L)-1)
    cnt = 0
    aap = 0
    for aa in A_sorted[i:]:
        if aap==aa: continue
        aap = aa
        for v in d[aa]:
            if L[v] >= K:
                L[v] -= 1
                cnt += 1
        if cnt >= Q:
            break
    else:
        break
    ans = min(ans, aa-a)
print(ans)

Submission status: Accepted

Solution code:
n,k,q = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
ans = 10**9
for i in a:
	p,s,f = [],0,1
	for j in range(n):
		if a[j]>=i and f:
			s,f = j,0
		elif a[j]<i and f-1:
			if j-s>=k:
				for j2 in sorted(a[s:j])[:j-s-k+1]: p.append(j2)
			f = 1
	if f-1 and n-s>=k:
		for j2 in sorted(a[s:n])[:n-s-k+1]: p.append(j2)
	if len(p)>=q: ans = min(ans,sorted(p)[q-1]-i)
print(ans)

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import *
from bisect import *

def read():
  return int(input())
 
def reads():
  return [int(x) for x in input().split()]

INF = 1 << 60

N, K, Q = reads()
A = reads()

A.append(-INF)
def getlub(y):
  v = []
  l = 0
  for i in range(N+1):
    if A[i] < y:
      w = A[l:i]
      w.sort()
      if len(w) >= K-1:
        v.extend(w[:len(w)-K+1])
      l = i + 1
  v.sort()
  return v[Q-1] if len(v) >= Q else INF

ans = INF
for Y in A[:-1]:
  X = getlub(Y)
  ans = min(ans, X - Y)
print(ans)

Submission status: Accepted

Solution code:
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))

d = [a]
a = sorted(a)
a.sort()
ans = a[Q-1] - a[0]

while True:
  d_temp = list()
  sub_temp = list()
  for sub in d:
    for c in sub:
      if c != a[0]:
        sub_temp.append(c)
      else:
        d_temp.append(sub_temp)
        sub_temp = list()
    d_temp.append(sub_temp)
    sub_temp = list()

  d = list()
  a = list()
  for sub in d_temp:
    if len(sub) < K:
      continue
    else:
      d.append(sub)
      sub = sorted(sub)
      a.extend(sub[0:len(sub)-K+1])

  a = sorted(a)

  if len(a) < Q:
    break
  else:
    ans = min(ans, a[Q-1] - a[0])

print(ans)

Submission status: Accepted

Solution code:
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))

d = [a]
a = sorted(a)
ans = a[Q-1] - a[0]

while True:
  d_temp = list()
  sub_temp = list()
  for sub in d:
    for c in sub:
      if c != a[0]:
        sub_temp.append(c)
      else:
        d_temp.append(sub_temp)
        sub_temp = list()
    d_temp.append(sub_temp)
    sub_temp = list()

  d = list()
  a = list()
  for sub in d_temp:
    if len(sub) < K:
      continue
    else:
      d.append(sub)
      sub = sorted(sub)
      a.extend(sub[0:len(sub)-K+1])

  a = sorted(a)

  if len(a) < Q:
    break
  else:
    ans = min(ans, a[Q-1] - a[0])

print(ans)

Submission status: Accepted

Solution code:
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))

d=[a]
a = sorted(a)

ans = a[Q-1] - a[0]


while True:
  d_temp = list()
  sub_temp = list()
  for sub in d:
    for c in sub:
      if c != a[0]:
        sub_temp.append(c)
      else:
        d_temp.append(sub_temp)
        sub_temp = list()
    d_temp.append(sub_temp)
    sub_temp = list()

  d = list()
  a = list()
  for sub in d_temp:
    if len(sub) < K:
      continue
    else:
      d.append(sub)
      sub = sorted(sub)
      a.extend(sub[0:len(sub)-K+1])

  a.sort()

  if len(a) < Q:
    break
  else:
    ans = min(ans, a[Q-1] - a[0])

print(ans)

Submission status: Accepted

Solution code:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
 
d = [a]
a = sorted(a)
ans = a[q - 1] - a[0]
 
while True:
    newd = list()
    li = list()
    for sub in d:
        for c in sub:
            if c != a[0]:
                li.append(c)
            else:
                newd.append(li)
                li = list()
        newd.append(li)
        li = list()
 
    d = list()
    a = list()
    for li in newd:
        if len(li) < k:
            continue
        else:
            d.append(li)
            li = sorted(li)
            a.extend(li[0:len(li) - k + 1])
 
    a.sort()
 
    if len(a) >= q:
        ans = min(a[q - 1] - a[0], ans)
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))
 
d = [a]
a = sorted(a)
ans = a[q - 1] - a[0]
 
while True:
    newd = list()
    li = list()
    for sub in d:
        for c in sub:
            if c != a[0]:
                li.append(c)
            else:
                newd.append(li)
                li = list()
        newd.append(li)
        li = list()
 
    d = list()
    a = list()
    for li in newd:
        if len(li) < k:
            continue
        else:
            d.append(li)
            li = sorted(li)
            a.extend(li[0:len(li) - k + 1])
 
    a.sort()
 
    if len(a) >= q:
        ans = min(a[q - 1] - a[0], ans)
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
N, K, Q = map(int, input().split())
As = list(map(int, input().split()))

ans = 10 ** 9
for Y in sorted(As)[:N - Q - K + 2]:
    cands = []
    cs = []
    for A in As + [0]: # 最終要素は番兵
        if A < Y:
            if len(cs) >= K:
                cands += sorted(cs)[:len(cs) - K + 1]
            cs = []
        else:
            cs += [A]

    if len(cands) < Q: continue
    X = sorted(cands)[Q - 1]

    ans = min(ans, X - Y)

print(ans)

Submission status: Accepted

Solution code:
from heapq import *
N, K, Q = map(int, input().split())
a = list(map(int, input().split()))
b = [None]*(N+2)
x = []

def merge(q1, q2):
    if q1 < q2:
        q1, q2 = q2, q1
    s = q1[0] + q2[0]
    while q2[1]:
        add(q1, heappop(q2[1]))
    q1[0] = s
    return q1

def add(q, v):
    q[0] += 1
    w = push(q[1], K-1, v)
    if w:
        push(x, Q, -w)

def push(q, m, v):
    if len(q) < m:
        heappush(q, v)
        return
    return heappushpop(q, v)

r = 10**9
for i in sorted(range(1, N+1), key=lambda x: -a[x-1]):
    if b[i-1] and b[i+1]:
        s, t = b[i-1][0], b[i+1][0]
        b[i-s] = b[i+t] = merge(b[i-1], b[i+1])
        add(b[i-s], a[i-1])
        b[i] = 1
    elif b[i-1]:
        add(b[i-1], a[i-1])
        b[i] = b[i-1]
    elif b[i+1]:
        add(b[i+1], a[i-1])
        b[i] = b[i+1]
    else:
        b[i] = [0,[]]
        add(b[i], a[i-1])
    if len(x) == Q:
        r = min(r, -x[0]-a[i-1])
print(r)

Submission status: Accepted

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A) # A をソート
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)] # BからX-Yの最小パターンを出す
sL = sorted(L,key=lambda x:x[1]) # Lをソート

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()

if Q == N - K + 1:
    # 全部の要素が選ばれる = 必ず最小値が選ばれる
    print(L[0][1])
    exit()

if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

if sL[0][1] == sL[len(sL)-1][1]:
    print(sL[0][1])
    exit()


for key,value in sL:
    max_value = B[key + Q - 1]
    min_value = B[key]
    C = [(i if i >= min_value else None) for i in A]
    i = 0
    j = 0
    count = 0
    min_OK = max_OK = False
    while i < N:
        if not C[i]:
            i += 1
            continue
        j = i + 1
        while j < N:
            if not C[j]:
                break
            j += 1
        tmp = (j-i) - K + 1
        if  tmp < 1:
            # 要素を取得できないパターン
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if not min_OK and (sC[0] == min_value):
            min_OK = True
        if not max_OK and max_value in sC[0:tmp]:
            max_OK = True
        count += tmp - len([i for i in sC[:tmp] if i > max_value])
        i = j +1
    if min_OK and max_OK and (count >= Q):
        print(value)
        exit()

print(L[0][1])

Submission status: Accepted

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
B = sorted(A) # A をソート
L = [[i,B[i+Q-1] - B[i]] for i in range(N-Q+1)] # BからX-Yの最小パターンを出す
sL = sorted(L,key=lambda x:x[1]) # Lをソート

if Q == 1:
    # 一つしか選ばない -> max == min -> 0
    print(0)
    exit()

if Q == N - K + 1:
    # 全部の要素が選ばれる = 必ず最小値が選ばれる
    print(L[0][1])
    exit()

if K == 1:
    # 一つずつ選べる -> 必ず最小のパターンに出来る
    print(sL[0][1])
    exit()

if sL[0][0] == 0:
    # minが最小の時 最小のパターンになる時
    print(sL[0][1])
    exit()

if sL[0][1] == sL[len(sL)-1][1]:
    print(sL[0][1])
    exit()

now_max_value = -1
now_min_value = -1
now_min_XY = int(1e10)

for key,value in sL:
    max_value = B[key + Q - 1]
    min_value = B[key]
    C = [(i if i >= min_value else None) for i in A]
    i = 0
    j = 0
    count = 0
    min_OK = max_OK = False
    while i < N:
        if not C[i]:
            i += 1
            continue
        j = i + 1
        while j < N:
            if not C[j]:
                break
            j += 1
        tmp = (j-i) - K + 1
        if  tmp < 1:
            # 要素を取得できないパターン
            #if min(C[i:j]) < max_value:
            #    count = 0
            #    break
            i = j + 1
            continue
        sC = sorted(C[i:j])
        if not min_OK and (sC[0] == min_value):
            min_OK = True
        if not max_OK and max_value in sC[0:tmp]:
            max_OK = True
        #if sC[tmp] < max_value:
        #    count = 0
        #    break
        count += tmp - len([i for i in sC[:tmp] if i > max_value])
        i = j +1
    if min_OK and max_OK and (count >= Q):
        print(value)
        exit()
    now_min_XY = min(now_min_XY,now_max_value - now_min_value)
    now_max_value = -1
    now_min_value = -1

print(L[0][1])

Submission status: Accepted

Solution code:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))

d = [a]
a = sorted(a)
ans = a[q - 1] - a[0]

while True:
    newd = list()
    li = list()
    for sub in d:
        for c in sub:
            if c != a[0]:
                li.append(c)
            else:
                newd.append(li)
                li = list()
        newd.append(li)
        li = list()

    d = list()
    a = list()
    for li in newd:
        if len(li) < k:
            continue
        else:
            d.append(li)
            li = sorted(li)
            a.extend(li[0:len(li) - k + 1])
 
    a.sort()

    if len(a) >= q:
        ans = min(a[q - 1] - a[0], ans)
    else:
        break
print(ans)

Submission status: Accepted

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))

R = sorted(set(A))
ans = 10**9
for i in range(len(R)):
    temp = []
    temp2 = []
    l = 0
    for j in range(N):
        if A[j] < R[i]:
            if l >= K:
                temp += sorted(temp2)[:min(l,max(0,l - K + 1))]
            temp2 = []
            l = 0
        else:
            temp2.append(A[j])
            l += 1
    if l >= K:
        temp += sorted(temp2)[:min(l,max(0,l - K + 1))]

    if len(temp) > Q - 1:
        temp = sorted(temp)
        ans = min(ans,temp[Q - 1] - R[i])
    else:
        break
        
print(ans)

Submission status: Accepted

Solution code:
from heapq import nsmallest


def get_add_list():
    cache = {}

    def add_list(s, t):
        global new_lists, removables
        l = t - s
        if l >= k:
            new_lists.append((s, t))

            if (s, t) in cache:
                removables.extend(cache[s, t])
                return

            cache[s, t] = nsmallest(l - k + 1, aaa[s:t])
            removables.extend(cache[s, t])

    return add_list


n, k, q = map(int, input().split())
aaa = list(map(int, input().split()))
srt = sorted(set(aaa))
lists = [(0, n)]
ans = float('inf')
add_list = get_add_list()
for a in srt:
    new_lists = []
    removables = []
    for s, t in lists:
        r = s
        for i, b in enumerate(aaa[s:t]):
            if a > b:
                add_list(r, s + i)
                r = s + i + 1
        add_list(r, t)
    if len(removables) < q:
        break
    removables.sort()
    ans = min(ans, removables[q - 1] - a)
    lists = new_lists

print(ans)

Submission status: Accepted

Solution code:
def add_list(buf, new_lists, removals):
    l = len(buf)
    if l >= k:
        sbf = sorted(buf)
        removals.extend(sbf[:l - k + 1])
        new_lists.append(buf)


n, k, q = map(int, input().split())
aaa = list(map(int, input().split()))
srt = sorted(set(aaa))
lists = [aaa]
ans = float('inf')
for a in srt:
    new_lists = []
    removals = []
    for lst in lists:
        buf = []
        for b in lst:
            if a > b:
                add_list(buf, new_lists, removals)
                buf = []
            else:
                buf.append(b)
        add_list(buf, new_lists, removals)
    if len(removals) < q:
        break
    removals.sort()
    ans = min(ans, removals[q - 1] - a)
    lists = new_lists

print(ans)

Submission status: Accepted

Solution code:
def add_list(buf, new_lists, removals):
    l = len(buf)
    if l >= k:
        sbf = sorted(buf)
        removals.extend(sbf[:l - k + 1])
        new_lists.append(buf)


n, k, q = map(int, input().split())
aaa = list(map(int, input().split()))
srt = sorted(set(aaa))
lists = [aaa]
ans = float('inf')
for a in srt:
    new_lists = []
    removals = []
    for lst in lists:
        buf = []
        for b in lst:
            if a > b:
                add_list(buf, new_lists, removals)
                buf = []
            else:
                buf.append(b)
        add_list(buf, new_lists, removals)
    if len(removals) < q:
        break
    removals.sort()
    ans = min(ans, removals[q - 1] - a)

print(ans)

Submission status: Accepted

Solution code:
def add_list(buf, new_lists, removals):
    l = len(buf)
    if l >= k:
        sbf = sorted(buf)
        removals.extend(sbf[:l - k + 1])
        new_lists.append(buf)


n, k, q = map(int, input().split())
aaa = list(map(int, input().split()))
srt = sorted(aaa)
lists = [aaa]
ans = float('inf')
for a in srt:
    new_lists = []
    removals = []
    for lst in lists:
        buf = []
        for b in lst:
            if a > b:
                add_list(buf, new_lists, removals)
                buf = []
            else:
                buf.append(b)
        add_list(buf, new_lists, removals)
    if len(removals) < q:
        break
    removals.sort()
    ans = min(ans, removals[q - 1] - a)

print(ans)

Submission status: Accepted

Solution code:
N,K,Q = map(int,input().split())
A = list(map(int,input().split()))
SA = sorted(A)

def calc_max_a(min_a):
    cands = []
    seq = 0
    for i,a in enumerate(A):
        if a < min_a:
            if seq >= K:
                cands += sorted(A[i-seq:i])[:seq-K+1]
            seq = 0
        else:
            seq += 1
    if seq >= K:
        cands += sorted(A[-seq:])[:seq-K+1]
    if len(cands) < Q:
        return -1
    else:
        return sorted(cands)[Q-1]

min_a = 0
ans = float('inf')
for a in SA:
    if a == min_a: continue
    min_a = a
    max_a = calc_max_a(min_a)
    if max_a < 0: break
    ans = min(ans, max_a - min_a)
print(ans)

Submission status: Accepted

Solution code:
import heapq

def main():
    _, k, q = map(int, input().split())
    a = list(map(int, input().split()))
    idx = make_index(a)
    groups = [(0, len(a))]

    m = float('inf')
    for y in sorted(set(a)):
        xs = []
        for start, stop in groups:
            xs.extend(nsmallest(min(stop - start - k + 1, q), a, start, stop))

        if len(xs) < q:
            break

        xxs = heapq.nsmallest(q, xs)
        x = xxs[-1]
        m = min(m, x - y)

        groups = split_groups(idx[y], groups, k)

    print(m)

MEMO = dict()
def nsmallest(n, a, start, stop):
    global MEMO
    key = (n, id(a), start, stop)
    if key in MEMO:
        return MEMO[key]

    val = heapq.nsmallest(n, a[start:stop])
    MEMO[key] = val
    return val

def split_groups(pivots, groups, k):
    gs = []

    i = 0
    for start, stop in groups:
        while i < len(pivots) and pivots[i] < start:
            i += 1
        while i < len(pivots) and pivots[i] <= stop:
            if pivots[i] - start >= k:
                gs.append((start, pivots[i]))
            start = pivots[i] + 1
            i += 1

        if stop - start >= k:
            gs.append((start, stop))

    return gs


def make_index(a):
    idx = dict()

    for i, x in enumerate(a):
        if x in idx:
            idx[x].append(i)
        else:
            idx[x] = [i]

    return idx

main()

Submission status: Accepted

Solution code:
n, k, q = map(int, input().split())
a = list(map(int, input().split()))

set_a = sorted(set(a))

result = 1000000000
for y in set_a:
    counter = 0
    candidate = []
    for i in range(n):
#        print(counter, a[i], y)
        if a[i] < y:
            if counter >= k:
#                print(a[i-counter:i-1])
                candidate = candidate + sorted(a[i-counter:i])[:counter - k + 1]
            counter = 0
        elif i == n - 1:
            if counter + 1 >= k:
                candidate = candidate + sorted(a[i-counter:i+1])[:counter - k + 2]
        else:
            counter += 1
#    print(candidate)
    if len(candidate) >= q:
        z = sorted(candidate)[q - 1] - y
        if z < result:
            result = z

print(result)

Submission status: Accepted

Solution code:
import heapq

def main():
    _, k, q = map(int, input().split())
    a = list(map(int, input().split()))
    idx = make_index(a)
    groups = [(0, len(a))]

    m = float('inf')
    for y in sorted(set(a)):
        xs = []
        for start, stop in groups:
            xs.extend(nsmallest(stop - start - k + 1, a, start, stop))

        if len(xs) < q:
            break

        xxs = heapq.nsmallest(q, xs)
        x = xxs[-1]
        m = min(m, x - y)

        groups = split_groups(idx[y], groups, k)

    print(m)

MEMO = dict()
def nsmallest(n, a, start, stop):
    global MEMO
    key = (n, id(a), start, stop)
    if key in MEMO:
        return MEMO[key]

    val = heapq.nsmallest(n, a[start:stop])
    MEMO[key] = val
    return val

def split_groups(pivots, groups, k):
    gs = []

    i = 0
    for start, stop in groups:
        while i < len(pivots) and pivots[i] < start:
            i += 1
        while i < len(pivots) and pivots[i] <= stop:
            if pivots[i] - start >= k:
                gs.append((start, pivots[i]))
            start = pivots[i] + 1
            i += 1

        if stop - start >= k:
            gs.append((start, stop))

    return gs


def make_index(a):
    idx = dict()

    for i, x in enumerate(a):
        if x in idx:
            idx[x].append(i)
        else:
            idx[x] = [i]

    return idx

main()

Submission status: Accepted

Solution code:
N, K, Q = map(int, input().split())
A = list(map(int, input().split()))

ans = float('inf')
for X in A:  # 下限候補

    # 下限候補未満の数で分割
    S = " ".join([(str(a) if a >= X else "x") for a in A])
    S = [list(map(int, Sx.split())) for Sx in S.split("x")]

    # Max候補を列挙
    C = []
    for s in S:
        s.sort(reverse=True)
        if len(s) >= K:
            for ss in s[K-1:]:
                C.append(ss)

    # Max候補の中の小さいほうからQ番目がMax
    C.sort()
    if len(C) >= Q:
        ans = min(ans, C[Q-1]-X)

print(ans)