E: Range Minimum Queries - AtCoder Regular Contest 098

取り出したQ個の要素の最小値miについてmi>=A[i]が成り立つとする。

このとき、Aのmi未満の要素は使えないので*の記号で表すと

{A[0], A[1]}, *, {A[3]} , *, *, {A[6], A[7], A[8]}, *, {A[10]}

のように*でAの要素がいくつかのグループに分けられる。このグループの中で K個以上要素を含むものから小さい要素を貪欲に取っていけば、最小値と最大値がともに求まる。

const int INF = 1 << 30;
int N, K, Q;
cin >> N >> K >> Q;
vi A(N);
each(a, A)cin >> a;
priority_queue<int, vector<int>, greater<int> > pq;
int re = INF;
each(mi, A) {
    vi B;
    rep(b, N+1) {
        if (b<N && A[b] >= mi) {
            B.push_back(A[b]);
        } else {
            if (sz(B) >= K) {
                sort(all(B));
                for (int c = 0; c + K <= sz(B); ++c) {
                    pq.push(B[c]);
                }
            }
            B.clear();
        }
    }
    if (sz(pq) >= Q) {
        int ma = -1;
        rep(c, Q) {
            ma = pq.top();
            pq.pop();
        }
        smin(re, ma - mi);
    }
    while (sz(pq)) pq.pop();
}
cout << re << endl;