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
AC × 3
AC × 54
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