Language: C++

#include <cassert>
#include <cstddef>
#include <numeric>
#include <utility>
#include <vector>

class UnionFind {

public:
  using size_type = std::size_t;
  using container_type = std::vector<size_type>;

protected:
  container_type p, s;

public:
  UnionFind() : p(), s() {}
  explicit UnionFind(const size_type size)
      : p(size), s(size, static_cast<size_type>(1)) {
    std::iota(p.begin(), p.end(), static_cast<size_type>(0));
  }

  size_type size() const { return p.size(); }
  bool empty() const { return p.empty(); }

  size_type find(size_type x) {
    assert(x < size());
    while (p[x] != x)
      x = p[x] = p[p[x]];
    return x;
  }
  bool same(const size_type x, const size_type y) {
    assert(x < size());
    assert(y < size());
    return find(x) == find(y);
  }
  size_type size(const size_type x) {
    assert(x < size());
    return s[find(x)];
  }

  std::pair<size_type, size_type> unite(size_type x, size_type y) {
    assert(x < size());
    assert(y < size());
    x = find(x);
    y = find(y);
    if (x != y) {
      if (s[x] < s[y])
        std::swap(x, y);
      s[x] += s[y];
      p[y] = x;
    }
    return {x, y};
  }
};

#include <cassert>
#include <functional>
#include <utility>
#include <vector>

template <typename T, class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type>>
class IntervalHeap {

public:
  using container_type = Container;
  using value_compare = Compare;
  using value_type = typename container_type::value_type;
  using reference = typename container_type::reference;
  using const_reference = typename container_type::const_reference;
  using size_type = typename container_type::size_type;

protected:
  container_type c;
  value_compare comp;

private:
  static constexpr size_type z = ~static_cast<size_type>(1);
  bool normalize(const size_type x, const size_type y) {
    if (!comp(c[y], c[x]))
      return false;
    std::swap(c[x], c[y]);
    return true;
  }
  void build() {
    const size_type s = size() + 1;
    if (s & 1) {
      normalize(s & z, s);
      buildmin(s >> 1);
      buildmax(s >> 1);
      return;
    }
    if (s == 2)
      return;
    if (normalize(s, s >> 1 | 1))
      buildmax(s >> 2);
    buildmin(s >> 1);
  }
  void buildmin(size_type i) {
    while (i > 1 && normalize(i & z, i << 1))
      i >>= 1;
  }
  void buildmax(size_type i) {
    while (i > 1 && normalize(i << 1 | 1, i | 1))
      i >>= 1;
  }

public:
  explicit IntervalHeap(const value_compare &x = value_compare())
      : c(2), comp(x) {}
  bool empty() const { return c.size() == 2; }
  size_type size() const { return c.size() - 2; }
  const_reference min() const {
    assert(!empty());
    return c[2];
  }
  const_reference max() const {
    assert(!empty());
    return size() == 1 ? c[2] : c[3];
  }
  void push(const value_type &x) {
    c.push_back(x);
    build();
  }
  void push(value_type &&x) {
    c.push_back(std::move(x));
    build();
  }
  template <class... Args> void emplace(Args &&... args) {
    c.emplace_back(std::forward<Args>(args)...);
    build();
  }
  void pop_min() {
    assert(!empty());
    const size_type s = size() + 1;
    std::swap(c[2], c[s]);
    c.pop_back();
    size_type i = 4;
    while (i < s) {
      if ((i | 2) < s && !comp(c[i], c[i | 2]))
        i |= 2;
      if (!normalize(i >> 1 & z, i))
        return;
      if ((i | 1) < s)
        normalize(i, i | 1);
      i <<= 1;
    }
  }
  void pop_max() {
    assert(!empty());
    const size_type s = size() + 1;
    if (s == 2)
      return pop_min();
    std::swap(c[3], c[s]);
    c.pop_back();
    size_type i = 5;
    while (i < s) {
      if ((i | 2) < s && !comp(c[i | 2], c[i]))
        i |= 2;
      if (!normalize(i, i >> 1 | 1))
        return;
      normalize(i & z, i);
      i = (i & z) << 1 | 1;
    }
  }
};

#include <functional>
#include <queue>
#include <utility>
#include <vector>

template <class T, class Container = std::vector<T>,
          class Compare = std::less<typename Container::value_type>>
class meld_priority_queue : public std::priority_queue<T, Container, Compare> {

  void cascade_up(const size_type i) {
    const size_type l = i * 2 + 1;
    const size_type r = i * 2 + 2;
    if (r < c.size() && comp(c[l], c[r])) {
      if (comp(c[i], c[r])) {
        std::swap(c[i], c[r]);
      }
    } else {
      if (comp(c[i], c[l])) {
        std::swap(c[i], c[l]);
      }
    }
  }

public:
  template <class... Args>
  meld_priority_queue(Args &&... args)
      : priority_queue(std::forward<Args>(args)...) {}

  void meld(meld_priority_queue &&x) {
    if (x.empty()) {
      return;
    }
    size_type l = c.size();
    for (value_type &v : x.c) {
      c.push_back(std::move(v));
    }
    size_type r = c.size() - 1;
    while (r != 0) {
      l = (l - 1) / 2;
      r = (r - 1) / 2;
      for (size_type i = l; i <= r; ++i) {
        cascade_up(i);
      }
    }
  }
};

#include <algorithm>
#include <iostream>
#include <limits>
#include <numeric>
#include <tuple>
#include <vector>

int main() {
  int n, k, q;
  std::cin >> n >> k >> q;
  std::vector<int> a(n), b(n);
  for (auto &e : a)
    std::cin >> e;
  std::iota(b.begin(), b.end(), 0);
  std::sort(b.begin(), b.end(), [&](int x, int y) { return a[x] > a[y]; });

  std::vector<char> used(n, 0);
  UnionFind T(n);
  IntervalHeap<int> H;
  std::vector<meld_priority_queue<int, std::vector<int>, std::greater<int>>>
      heaps(n);
  int ans = std::numeric_limits<int>::max();
  for (int i = 0; i < n; ++i)
    heaps[i].emplace(a[i]);
  for (const auto i : b) {
    used[i] = 1;
    if (i != 0 && used[i - 1]) {
      int x, y;
      std::tie(x, y) = T.unite(i, i - 1);
      if (heaps[x].size() < heaps[y].size()) {
        std::swap(heaps[x], heaps[y]);
      }
      heaps[x].meld(std::move(heaps[y]));
    }
    if (i != n - 1 && used[i + 1]) {
      int x, y;
      std::tie(x, y) = T.unite(i, i + 1);
      if (heaps[x].size() < heaps[y].size()) {
        std::swap(heaps[x], heaps[y]);
      }
      heaps[x].meld(std::move(heaps[y]));
    }
    auto &t = heaps[T.find(i)];
    while (t.size() >= k) {
      H.emplace(t.top());
      t.pop();
    }
    if (H.size() >= q) {
      while (H.size() > q)
        H.pop_max();
      ans = std::min(ans, H.max() - H.min());
    }
  }

  std::cout << ans << std::endl;

  return 0;
}


Compiler output:
a.cc:178:25: error: 'size_type' does not name a type; did you mean 'size_t'?
  178 |   void cascade_up(const size_type i) {
      |                         ^~~~~~~~~
      |                         size_t
a.cc:178:25: note: (perhaps 'typename std::priority_queue<_Tp, _Sequence, _Compare>::size_type' was intended)
a.cc: In member function 'void meld_priority_queue<T, Container, Compare>::cascade_up(int)':
a.cc:179:11: error: 'size_type' does not name a type; did you mean 'size_t'?
  179 |     const size_type l = i * 2 + 1;
      |           ^~~~~~~~~
      |           size_t
a.cc:179:11: note: (perhaps 'typename std::priority_queue<_Tp, _Sequence, _Compare>::size_type' was intended)
a.cc:180:11: error: 'size_type' does not name a type; did you mean 'size_t'?
  180 |     const size_type r = i * 2 + 2;
      |           ^~~~~~~~~
      |           size_t
a.cc:180:11: note: (perhaps 'typename std::priority_queue<_Tp, _Sequence, _Compare>::size_type' was intended)
a.cc:181:9: error: 'r' was not declared in this scope
  181 |     if (r < c.size() && comp(c[l], c[r])) {
      |         ^
a.cc:181:13: error: 'c' was not declared in this scope
  181 |     if (r < c.size() && comp(c[l], c[r])) {
      |             ^
a.cc:181:32: error: 'l' was not declared in this scope
  181 |     if (r < c.size() && comp(c[l], c[r])) {
      |                                ^
a.cc:181:25: error: there are no arguments to 'comp' that depend on a template parameter, so a declaration of 'comp' must be available [-fpermissive]
  181 |     if (r < c.size() && comp(c[l], c[r])) {
      |                         ^~~~
a.cc:181:25: note: (if you use '-fpermissive', G++ will accept your code, but allowing the use of an undeclared name is deprecated)
a.cc:182:11: error: there are no arguments to 'comp' that depend on a template parameter, so a declaration of 'comp' must be available [-fpermissive]
  182 |       if (comp(c[i], c[r])) {
      |           ^~~~
a.cc:186:11: error: there are no arguments to 'comp' that depend on a template parameter, so a declaration of 'comp' must be available [-fpermissive]
  186 |       if (comp(c[i], c[l])) {
      |           ^~~~
a.cc: In constructor 'meld_priority_queue<T, Container, Compare>::meld_priority_queue(Args&& ...)':
a.cc:195:9: error: class 'meld_priority_queue<T, Container, Compare>' does not have any field named 'priority_queue'
  195 |       : priority_queue(std::forward<Args>(args)...) {}
      |         ^~~~~~~~~~~~~~
a.cc: In member function 'void meld_priority_queue<T, Container, Compare>::meld(meld_priority_queue<T, Container, Compare>&&)':
a.cc:201:5: error: 'size_type' was not declared in this scope; did you mean 'size_t'?
  201 |     size_type l = c.size();
      |     ^~~~~~~~~
      |     size_t
a.cc:202:10: error: 'value_type' was not declared in this scope
  202 |     for (value_type &v : x.c) {
      |          ^~~~~~~~~~
a.cc:202:24: error: found ':' in nested-name-specifier, expected '::'
  202 |     for (value_type &v : x.c) {
      |                        ^
      |                        ::
a.cc:202:22: error: 'v' has not been declared
  202 |     for (value_type &v : x.c) {
      |                      ^
a.cc:205:15: error: expected ';' before 'r'
  205 |     size_type r = c.size() - 1;
      |               ^
a.cc:205:15: error: 'r' was not declared in this scope
a.cc:205:19: error: 'c' was not declared in this scope
  205 |     size_type r = c.size() - 1;
      |                   ^
a.cc:205:31: error: expected ')' before ';' token
  205 |     size_type r = c.size() - 1;
      |                               ^
a.cc:202:9: note: to match this '('
  202 |     for (value_type &v : x.c) {
      |         ^
a.cc:206:12: error: 'r' was not declared in this scope
  206 |     while (r != 0) {
      |            ^
a.cc:207:7: error: 'l' was not declared in this scope
  207 |       l = (l - 1) / 2;
      |       ^
a.cc:209:22: error: expected ';' before 'i'
  209 |       for (size_type i = l; i <= r; ++i) {
      |                      ^
a.cc:209:29: error: 'i' was not declared in this scope
  209 |       for (size_type i = l; i <= r; ++i) {
      |                             ^
a.cc: In instantiation of 'void meld_priority_queue<T, Container, Compare>::cascade_up(int) [with T = int; Container = std::vector<int>; Compare = std::greater<int>]':
a.cc:210:9:   required from 'void meld_priority_queue<T, Container, Compare>::meld(meld_priority_queue<T, Container, Compare>&&) [with T = int; Container = std::vector<int>; Compare = std::greater<int>]'
  210 |         cascade_up(i);
      |         ^~~~~~~~~~
a.cc:248:20:   required from here
  248 |       heaps[x].meld(std::move(heaps[y]));
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
a.cc:181:40: error: 'comp' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
  181 |     if (r < c.size() && comp(c[l], c[r])) {
      |                                        ^
a.cc:182:26: error: 'comp' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
  182 |       if (comp(c[i], c[r])) {
      |                          ^
a.cc:186:26: error: 'comp' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation
  186 |       if (comp(c[i], c[l])) {
      |                          ^