oj.uz

Submission #171794

# Submission time Handle Problem Language Result Execution time Memory
171794 2019-12-30T12:16:24 Z emil_physmath K blocks (IZhO14_blocks) C++17
53 / 100
 1000 ms 124792 KB 
#include <climits>
#include <cstdint>
#include <functional>
#include <iostream>
#include <vector>

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;
	std::cin >> N >> K;
	segment_tree a(N, 0);
	std::vector<int> arr(N);
	for (size_t i = 0; i < N; ++i)
	{
		std::cin >> arr[i];
		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;

	char I;
	std::cin >> I;
}

Compilation message

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

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 256 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 380 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 380 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 376 KB Output is correct
20 Correct 2 ms 376 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 504 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 428 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 380 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 3 ms 504 KB Output is correct
14 Correct 3 ms 504 KB Output is correct
15 Correct 5 ms 760 KB Output is correct
16 Correct 5 ms 632 KB Output is correct
17 Correct 4 ms 504 KB Output is correct
18 Correct 5 ms 760 KB Output is correct
19 Correct 5 ms 752 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 10488 KB Output is correct
2 Correct 367 ms 6776 KB Output is correct
3 Correct 541 ms 16248 KB Output is correct
4 Execution timed out 1094 ms 124792 KB Time limit exceeded
5 Halted 0 ms 0 KB -