Submission #2634033
Source Code Expand
#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 <cassert>
#include <cstddef>
#include <functional>
#include <memory>
#include <utility>
template <class T, class Compare = ::std::less_equal<T>>
class persistent_leftist_heap {
public:
using value_type = T;
using const_reference = const value_type &;
using size_type = ::std::size_t;
using value_compare = Compare;
private:
struct node_type {
using pointer = ::std::shared_ptr<const node_type>;
using cptr_cr = const pointer &;
value_type value;
size_type size;
pointer left, right;
template <class Lptr, class Rptr, class... Args>
explicit node_type(Lptr &&l, Rptr &&r, Args &&... args)
: value(::std::forward<Args>(args)...),
size(get_size(l) + get_size(r) + 1), left(::std::forward<Lptr>(l)),
right(::std::forward<Rptr>(r)) {}
};
using pointer = ::std::shared_ptr<const node_type>;
using cptr_cr = const pointer &;
static size_type get_size(cptr_cr x) noexcept { return x ? x->size : 0; }
static pointer make(const value_type &v, cptr_cr x, pointer &&y) {
if (get_size(x) >= get_size(y))
return ::std::make_shared<const node_type>(x, y, v);
else
return ::std::make_shared<const node_type>(y, x, v);
}
pointer merge(cptr_cr x, cptr_cr y) const {
if (!x)
return y;
if (!y)
return x;
if (comp(x->value, y->value))
return make(x->value, x->left, merge(x->right, y));
else
return make(y->value, y->left, merge(y->right, x));
}
pointer root;
value_compare comp;
explicit persistent_leftist_heap(pointer &&r, const value_compare &c)
: root(::std::move(r)), comp(c) {}
public:
persistent_leftist_heap() : root(), comp() {}
explicit persistent_leftist_heap(const value_compare &x) : root(), comp(x) {}
bool empty() const noexcept { return !root; }
size_type size() const noexcept { return get_size(root); }
const_reference top() const noexcept {
assert(!empty());
return root->value;
}
persistent_leftist_heap push(const value_type &x) const {
return persistent_leftist_heap(
merge(root,
::std::make_shared<const node_type>(pointer(), pointer(), x)),
comp);
}
persistent_leftist_heap push(value_type &&x) const {
return persistent_leftist_heap(
merge(root, ::std::make_shared<const node_type>(pointer(), pointer(),
::std::move(x))),
comp);
}
template <class... Args>
persistent_leftist_heap emplace(Args &&... args) const {
return persistent_leftist_heap(
merge(root, ::std::make_shared<const node_type>(
pointer(), pointer(), ::std::forward<Args>(args)...)),
comp);
}
persistent_leftist_heap pop() const {
assert(!empty());
return persistent_leftist_heap(merge(root->left, root->right), comp);
}
persistent_leftist_heap meld(const persistent_leftist_heap &x) const {
return persistent_leftist_heap(merge(root, x.root), comp);
}
persistent_leftist_heap operator+(const persistent_leftist_heap &x) const {
return persistent_leftist_heap(merge(root, x.root), comp);
}
};
#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<persistent_leftist_heap<int>> heaps(n);
int ans = ::std::numeric_limits<int>::max();
for (int i = 0;i < n;++i)
heaps[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);
heaps[x] = heaps[x] + heaps[y];
}
if (i != n - 1 && used[i + 1]) {
int x, y;
::std::tie(x, y) = T.unite(i, i + 1);
heaps[x] = heaps[x] + heaps[y];
}
auto &t = heaps[T.find(i)];
while (t.size() >= k) {
H.emplace(t.top());
t = 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;
}
Submission Info
Submission Time |
|
Task |
E - Range Minimum Queries |
User |
noshi91 |
Language |
C++14 (GCC 5.4.1) |
Score |
600 |
Code Size |
8065 Byte |
Status |
AC |
Exec Time |
4 ms |
Memory |
640 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
600 / 600 |
Status |
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
sample_03.txt |
AC |
1 ms |
256 KB |
subtask_1_01.txt |
AC |
1 ms |
256 KB |
subtask_1_02.txt |
AC |
1 ms |
256 KB |
subtask_1_03.txt |
AC |
2 ms |
384 KB |
subtask_1_04.txt |
AC |
1 ms |
256 KB |
subtask_1_05.txt |
AC |
1 ms |
256 KB |
subtask_1_06.txt |
AC |
2 ms |
256 KB |
subtask_1_07.txt |
AC |
2 ms |
512 KB |
subtask_1_08.txt |
AC |
3 ms |
512 KB |
subtask_1_09.txt |
AC |
2 ms |
384 KB |
subtask_1_10.txt |
AC |
2 ms |
384 KB |
subtask_1_11.txt |
AC |
3 ms |
512 KB |
subtask_1_12.txt |
AC |
2 ms |
512 KB |
subtask_1_13.txt |
AC |
3 ms |
512 KB |
subtask_1_14.txt |
AC |
3 ms |
640 KB |
subtask_1_15.txt |
AC |
3 ms |
512 KB |
subtask_1_16.txt |
AC |
3 ms |
640 KB |
subtask_1_17.txt |
AC |
2 ms |
512 KB |
subtask_1_18.txt |
AC |
2 ms |
512 KB |
subtask_1_19.txt |
AC |
2 ms |
512 KB |
subtask_1_20.txt |
AC |
2 ms |
512 KB |
subtask_1_21.txt |
AC |
2 ms |
512 KB |
subtask_1_22.txt |
AC |
2 ms |
512 KB |
subtask_1_23.txt |
AC |
3 ms |
512 KB |
subtask_1_24.txt |
AC |
3 ms |
512 KB |
subtask_1_25.txt |
AC |
3 ms |
512 KB |
subtask_1_26.txt |
AC |
3 ms |
512 KB |
subtask_1_27.txt |
AC |
3 ms |
512 KB |
subtask_1_28.txt |
AC |
3 ms |
512 KB |
subtask_1_29.txt |
AC |
2 ms |
512 KB |
subtask_1_30.txt |
AC |
3 ms |
512 KB |
subtask_1_31.txt |
AC |
3 ms |
640 KB |
subtask_1_32.txt |
AC |
3 ms |
512 KB |
subtask_1_33.txt |
AC |
3 ms |
640 KB |
subtask_1_34.txt |
AC |
2 ms |
640 KB |
subtask_1_35.txt |
AC |
4 ms |
640 KB |
subtask_1_36.txt |
AC |
3 ms |
640 KB |
subtask_1_37.txt |
AC |
3 ms |
640 KB |
subtask_1_38.txt |
AC |
2 ms |
640 KB |
subtask_1_39.txt |
AC |
3 ms |
640 KB |
subtask_1_40.txt |
AC |
3 ms |
640 KB |
subtask_1_41.txt |
AC |
3 ms |
640 KB |
subtask_1_42.txt |
AC |
3 ms |
640 KB |
subtask_1_43.txt |
AC |
3 ms |
640 KB |
subtask_1_44.txt |
AC |
3 ms |
640 KB |
subtask_1_45.txt |
AC |
2 ms |
640 KB |
subtask_1_46.txt |
AC |
3 ms |
640 KB |
subtask_1_47.txt |
AC |
3 ms |
640 KB |
subtask_1_48.txt |
AC |
3 ms |
640 KB |