제출 #171807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
171807		emil_physmath	K개의 묶음 (IZhO14_blocks)	C++17	53 / 100	1085 ms	124736 KiB

blocks

#include <climits>
#include <cstdint>
#include <functional>
#include <iostream>
#include <vector>

#define FAST_IO
#ifdef FAST_IO
char readchar() {
	char c = getchar();
	while (c <= 33) {
		c = getchar();
	}
	return c;
}
 
 
int readint() {
	char c = getchar();
	while (c <= 33) {
		c = getchar();
	}
	bool sign = false;
	if (c == '-') {
		sign = true;
		c = getchar();
	}
	int t = 0;
	while (c >= '0' && c <= '9') {
		t = (t << 3) + (t << 1) + c - '0';
		c = getchar();
	}
	return (sign ? -t : t);
}
#endif

class segment_tree
{
public:
	static const int INF = 200000000;

	segment_tree(size_t n_, int val = 0);
	void maximize(size_t l, size_t r, int val)
	{
		if (r >= n || l > r) throw;
		maximize_(1, 0, n - 1, l, r, val);
	}

	// Undefined behavior, if not all trees have equal segment_tree::n.
	friend void group_maximize(size_t l, size_t r,
		std::vector<segment_tree *> & trees, const std::vector<int> & val)
	{
		if (trees.empty()) return;
		if (trees.size() != val.size()) throw;
		if (r >= trees[0] -> n || l > r) throw;
		group_maximize_(1, 0, trees[0] -> n - 1, l, r, trees, val);
	}

	int operator[](size_t ind)
	{
		return at_ind(ind);
	}
	int at_ind(size_t ind)
	{
		if (ind >= n) throw;
		return at_ind_(1, 0, n - 1, ind);
	}
	int max_elem(size_t l, size_t r)
	{
		if (r >= n || l > r) throw;
		return max_elem_(1, 0, n - 1, l, r);
	}

	// Undefined behavior, if not all trees have equal segment_tree::n.
	friend void group_max_elem(size_t l, size_t r,
		std::vector<segment_tree *> & trees, std::vector<int> & res)
	{
		if (trees.empty()) return;
		if (r >= trees[0] -> n || l > r) throw;
		res.resize(trees.size(), -INF);
		return group_max_elem_(1, 0, trees[0] -> n - 1, l, r, trees, res);
	}

	void push(int v);
private:
	typedef std::int_least8_t ibool_t; // Stored in containers which don't fully support bool.

	void maximize_(int v, size_t vl, size_t vr, size_t l, size_t r, int val);
	friend void group_maximize_(int v, size_t vl, size_t vr, size_t l, size_t r,
		std::vector<segment_tree *> & trees, const std::vector<int> & val);
	int at_ind_(int v, size_t vl, size_t vr, size_t ind);
	int max_elem_(int v, size_t vl, size_t vr, size_t l, size_t r);
	friend void group_max_elem_(int v, size_t vl, size_t vr, size_t l, size_t r,
		std::vector<segment_tree *> & trees, std::vector<int> & res);

	size_t n;
	std::vector<int> tree;
	std::vector<ibool_t> is_lazy;
	std::vector<int> lazy;
};

segment_tree::segment_tree(size_t n_, int val):
	n(n_)
{
	try
	{
		if (!n) throw;
		tree.resize(n_ * 4, val);
		lazy.resize(n_ * 4, false);
		is_lazy.resize(n_ * 4, false);
	}
	catch (...)
	{
		std::abort();
	}
}

void segment_tree::maximize_(int v, size_t vl, size_t vr, size_t l, size_t r, int val)
{
	if (vl == l && vr == r)
	{
		if (!is_lazy[v] || val > lazy[v])
		{
			lazy[v] = val;
			is_lazy[v] = true;
		}
		return;
	}
	push(v);
	size_t vm = vl + (vr - vl) / 2;
	if (r <= vm)
		maximize_(2 * v, vl, vm, l, r, val);
	else if (l > vm)
		maximize_(2 * v + 1, vm + 1, vr, l, r, val);
	else
	{
		maximize_(2 * v, vl, vm, l, vm, val);
		maximize_(2 * v + 1, vm + 1, vr, vm + 1, r, val);
	}
	push(2 * v);
	push(2 * v + 1);
	if (tree[2 * v] > tree[v]) tree[v] = tree[2 * v];
	if (tree[2 * v + 1] > tree[v]) tree[v] = tree[2 * v + 1];
}

int segment_tree::at_ind_(int v, size_t vl, size_t vr, size_t ind)
{
	push(v);
	if (vl == vr)
		return tree[v];
	size_t vm = vl + (vr - vl) / 2;
	if (ind <= vm)
		return at_ind_(2 * v, vl, vm, ind);
	else
		return at_ind_(2 * v + 1, vm + 1, vr, ind);
}

int segment_tree::max_elem_(int v, size_t vl, size_t vr, size_t l, size_t r)
{
	push(v);
	if (vl == l && vr == r)
		return tree[v];
	size_t vm = vl + (vr - vl) / 2;
	if (r <= vm)
		return max_elem_(2 * v, vl, vm, l, r);
	else if (l > vm)
		return max_elem_(2 * v + 1, vm + 1, vr, l, r);
	else
	{
		return std::max(max_elem_(2 * v, vl, vm, l, vm),
			max_elem_(2 * v + 1, vm + 1, vr, vm + 1, r));
	}
}

void segment_tree::push(int v)
{
	if (is_lazy[v])
	{
		if (2 * v + 1 < tree.size())
		{
			is_lazy[2 * v] = is_lazy[2 * v + 1] = true;
			lazy[2 * v] = lazy[2 * v + 1] = lazy[v];
		}
		if (lazy[v] > tree[v]) tree[v] = lazy[v];
		is_lazy[v] = false;
	}
}

size_t max_fine(int l, int r, std:: function < bool(size_t) > is_fine)
{
	int st_l = l;
	while (l + 1 < r)
	{
		size_t m = l + (r - l) / 2;
		if (is_fine(m))
			l = m;
		else
			r = m - 1;
	}
	if (r >= st_l && is_fine(r)) return r;
	if (l >= st_l && is_fine(l)) return l;
	return r + 1;
}

size_t min_fine(size_t l, size_t r, std:: function < bool(size_t) > is_fine)
{
	size_t st_r = r;
	while (l + 1 < r)
	{
		size_t m = l + (r - l) / 2;
		if (is_fine(m))
			r = m;
		else
			l = m + 1;
	}
	if (l <= st_r && is_fine(l)) return l;
	if (r <= st_r && is_fine(r)) return r;
	return r + 1;
}

void group_max_elem_(int v, size_t vl, size_t vr, size_t l, size_t r,
	std::vector<segment_tree *> & trees, std::vector<int> & res)
{
	for (size_t i = 0; i < trees.size(); ++i)
		trees[i] -> push(v);
	if (vl == l && vr == r)
	{
		for (size_t i = 0; i < trees.size(); ++i)
			res[i] = std::max(res[i], trees[i] -> tree[v]);
		return;
	}
	size_t vm = vl + (vr - vl) / 2;
	if (r <= vm)
		group_max_elem_(2 * v, vl, vm, l, r, trees, res);
	else if (l > vm)
		group_max_elem_(2 * v + 1, vm + 1, vr, l, r, trees, res);
	else
	{
		group_max_elem_(2 * v, vl, vm, l, vm, trees, res);
		group_max_elem_(2 * v + 1, vm + 1, vr, vm + 1, r, trees, res);
	}
}

void group_maximize_(int v, size_t vl, size_t vr, size_t l, size_t r,
	std::vector<segment_tree *> & trees, const std::vector<int> & val)
{
	if (vl == l && vr == r)
	{
		for (size_t i = 0; i < trees.size(); ++i)
		{
			segment_tree & ST = *trees[i];
			if (!ST.is_lazy[v] || val[i] > ST.lazy[v])
			{
				ST.lazy[v] = val[i];
				ST.is_lazy[v] = true;
			}
		}
		return;
	}
	for (size_t i = 0; i < trees.size(); ++i)
		trees[i] -> push(v);
	size_t vm = vl + (vr - vl) / 2;
	if (r <= vm)
		group_maximize_(2 * v, vl, vm, l, r, trees, val);
	else if (l > vm)
		group_maximize_(2 * v + 1, vm + 1, vr, l, r, trees, val);
	else
	{
		group_maximize_(2 * v, vl, vm, l, vm, trees, val);
		group_maximize_(2 * v + 1, vm + 1, vr, vm + 1, r, trees, val);
	}
	for (size_t i = 0; i < trees.size(); ++i)
	{
		segment_tree &ST = *trees[i];
		ST.push(2 *v);
		ST.push(2 *v + 1);
		if (ST.tree[2 * v] > ST.tree[v])
			ST.tree[v] = ST.tree[2 * v];
		if (ST.tree[2 * v + 1] > ST.tree[v])
			ST.tree[v] = ST.tree[2 * v + 1];
	}
}

int main()
{
	// Fast input/output.
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);
	std::cout.tie(0);
	//
	size_t N, K;
#ifdef FAST_IO
    N = readint(); K = readint();
#else
	std::cin >> N >> K;
#endif
	segment_tree a(N, 0);
	std::vector<int> arr(N);
	for (size_t i = 0; i < N; ++i)
	{
#ifdef FAST_IO
        arr[i] = readint();
#else
		std::cin >> arr[i];
#endif
		a.maximize(i, i, arr[i]);
	}
	std::vector<segment_tree> dp(K + 1, segment_tree(N, -segment_tree::INF));
	for (size_t i = 0; i < N; ++i)
	{
		dp[1].maximize(i, i, -a.max_elem(0, i));
		size_t l = min_fine(0, i, [i, &arr, &a](size_t L) -> bool
		{
			return arr[i] >= a.max_elem(L, i);
		});

		std::vector<segment_tree *> trees;
		trees.reserve(std::min(K, i + 1));
		for (size_t k = 1; k < K && k <= i; ++k)
			trees.push_back(&dp[k]);
		std::vector<int> val;
		group_max_elem(l ? l - 1 : 0, i - 1, trees, val);
		for (size_t k = 1; k < K && k <= i; ++k)
			val[k - 1] = -(arr[i] + -val[k - 1]);
		
		trees.clear();
		for (size_t k = 2; k <= K && k <= i + 1; ++k)
			trees.push_back(&dp[k]);
		group_maximize(i, i, trees, val);
		size_t r = max_fine(i, N - 1, [i, &arr, &a](size_t R) -> bool
		{
			return arr[i] >= a.max_elem(i, R);
		});
		for (size_t k = 1; k <= K; ++k)
			dp[k].maximize(i, r, dp[k][i]);
#if 0 // DEBUG lines.
		for (size_t j = 0; j < N; ++j)
		{
			std::cerr << j << ": ";
			for (size_t k = 1; k <= K; ++k)
				if (-dp[k][j] < INF)
					std::cerr << -dp[k][j] << ' ';
				else
					std::cerr << "INF ";
			std::cerr << "\n";
		}
		std::cerr << "\n";
#endif // DEBUG lines.
	}
	int ans = segment_tree::INF;
	for (size_t i = 0; i < N; ++i)
		if (a.max_elem(i, N - 1) == arr[i])
			ans = std::min(ans, -dp[K][i]);
	std::cout << ans << std::endl;
}

컴파일 시 표준 에러 (stderr) 메시지

blocks.cpp: In member function 'void segment_tree::push(int)':
blocks.cpp:179:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (2 * v + 1 < tree.size())
       ~~~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 18 / 18
• Subtask 3: 21 / 21
• Subtask 4: 0 / 47