Submission #1050581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050581		aykhn	Comparing Plants (IOI20_plants)	C++17	100 / 100	778 ms	177672 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const long long MXN = 2e5 + 5;
const long long LOG = 20;

#define inf 0x3F3F3F3F
 
long long n;
array<long long, 2> p[2][LOG][MXN];
long long rr[MXN], f[MXN];
long long cnt[MXN];
array<long long, 2> st[MXN << 2];
long long lz[MXN << 2];

void build(long long l, long long r, long long x)
{
	if (l == r)
	{
		st[x] = {cnt[l] - rr[l], l};
		return;
	}
	long long mid = (l + r) >> 1;
	build(l, mid, 2*x);
	build(mid + 1, r, 2*x + 1);
	st[x] = min(st[2*x], st[2*x + 1]);
}
void relax(long long l, long long r, long long x)
{
	if (!lz[x]) return;
	st[x][0] += lz[x];
	if (l == r)
	{
		lz[x] = 0;
		return;
	}
	lz[2*x] += lz[x], lz[2*x + 1] += lz[x];
	lz[x] = 0;
}
void upd(long long l, long long r, long long x, long long lx, long long rx, long long val)
{
	if (lx > rx) return;
	relax(l, r, x);
	if (l > rx || r < lx) return;
	if (l >= lx && r <= rx)
	{
		lz[x] += val;
		relax(l, r, x);
		return;
	}
	long long mid = (l + r) >> 1;
	upd(l, mid, 2*x, lx, rx, val);
	upd(mid + 1, r, 2*x + 1, lx, rx, val);
	st[x] = min(st[2*x], st[2*x + 1]);
}

set<long long> idx;
set<array<long long, 2>> dif;

void ins(long long x)
{
	idx.insert(x);
	if (idx.size() == 1)
	{
		dif.insert({0, x});
		return;
	}
	auto it = idx.find(x);
	auto itl = it, itr = it;
	if (it == idx.begin()) itl = prev(idx.end());
	else itl = prev(it);
	if (next(it) == idx.end()) itr = idx.begin();
	else itr = next(it);
	dif.erase({(*itr - *itl + n) % n, *itr});
	dif.insert({(x - *itl + n) % n, x});
	dif.insert({(*itr - x + n) % n, *itr});
}
void ers(long long x)
{
	if (idx.size() == 1)
	{
		idx.clear();
		dif.clear();
		return;
	}
	auto it = idx.find(x);
	auto itl = it, itr = it;
	if (it == idx.begin()) itl = prev(idx.end());
	else itl = prev(it);
	if (next(it) == idx.end()) itr = idx.begin();
	else itr = next(it);
	dif.erase({(x - *itl + n) % n, x});
	dif.erase({(*itr - x + n) % n, *itr});
	dif.insert({(*itr - *itl + n) % n, *itr});
	idx.erase(it);
}
// 4 3 2
// 0 1 1 2
// 0 2
// 1 2

 
void init(int k, vector<int> r) 
{
	n = r.size();
	f[n] = inf;
	p[0][0][n] = {n, 0};
	p[1][0][n] = {n, 0};
	for (long long i = 1; i <= (n * 4); i++) st[i] = {inf, -1};
	for (long long i = 0; i < n; i++) rr[i] = r[i];
	for (long long i = 0; i < n; i++) cnt[i] = k - 1;
	build(0, n - 1, 1);
	while (1)
	{
		array<long long, 2> x = st[1];
		if (!x[0]) 
		{
			ins(x[1]);
			upd(0, n - 1, 1, x[1], x[1], inf);
		}
		else break;
	}
	long long cur = 0;
	while (!idx.empty())
	{
		long long ind = (*dif.rbegin())[1];
		ers(ind);
		f[ind] = ++cur;
		if (ind - 1 >= 0) upd(0, n - 1, 1, max(ind - k + 1, 0LL), ind - 1, -1);
		if (ind - k + 1 < 0) upd(0, n - 1, 1, (ind - k + 1 + n) % n, n - 1, -1);
		// for (long long i = (idx[ind] - 1 + n) % n; i != idx[(ind - 1 + sz) % sz]; i = (i - 1 + n) % n)
		// {
		// 	if (!f[i]) adj[idx[ind]].push_back(i);
		// }
		// for (long long i = (idx[ind] + 1) % n; i != (idx[ind] + k) % n; i = (i + 1) % n)
		// {
		// 	if (!f[i]) adj[idx[ind]].push_back(i);
		// }
		// for (long long i = (idx[ind] - 1 + n) % n; i != (idx[ind] - k + n) % n; i = (i - 1 + n) % n)
		// {
		// 	if (!f[i]) adj[idx[ind]].push_back(i);
		// 	cnt[i]--;
		// }
		// f[idx[ind]] = 1;
		while (1)
		{
			array<long long, 2> x = st[1];
			if (!x[0]) 
			{
				ins(x[1]);
				upd(0, n - 1, 1, x[1], x[1], inf);
			}
			else break;
		}
	}
	set<array<long long, 2>> s;
	for (long long i = 0; i < k; i++) s.insert({f[i], i});
	for (long long i = n - 1; i >= 0; i--)
	{
		s.erase({f[(i + k) % n], (i + k) % n});
		auto it = s.lower_bound({f[i], i});
		if (it != s.end()) 
		{
			p[0][0][i] = {(*it)[1], ((*it)[1] - i + n) % n};
		}
		else p[0][0][i] = {n, inf};
		s.insert({f[i], i});
	}
	s.clear();
	for (long long i = n - k; i < n; i++) s.insert({f[i], i});
	for (long long i = 0; i < n; i++)
	{
		s.erase({f[(i - k + n) % n], (i - k + n) % n});
		auto it = s.lower_bound({f[i], i});
		if (it != s.end()) 
		{
			p[1][0][i] = {(*it)[1], (i - (*it)[1] + n) % n};
		}
		else p[1][0][i] = {n, inf};
		s.insert({f[i], i});
	}
	// for (long long i = 0; i < n; i++)
	// {
	// 	cout << f[i] << ' ';
	// }
	// cout << '\n';
	// for (long long i = 0; i < n; i++)
	// {
	// 	cout << p[0][0][i][0] << ' ';
	// }
	// cout << '\n';
	// for (long long i = 0; i < n; i++)
	// {
	// 	cout << p[1][0][i][0] << ' ';
	// }
	// cout << '\n';
	for (long long j = 0; j < 2; j++)
	{
		for (long long i = 1; i < LOG; i++)
		{
			for (long long k = 0; k <= n; k++)
			{
				long long par = p[j][i - 1][k][0];
				p[j][i][k] = {p[j][i - 1][par][0], p[j][i - 1][par][1] + p[j][i - 1][k][1]};
			}
		}
	}
}

long long check(long long x, long long y)
{
	long long x1 = x;
	long long d = (y - x + n) % n;
	long long res = 0;
	for (long long i = LOG - 1; i >= 0; i--)
	{
		if (f[p[0][i][x][0]] <= f[y]) 
		{
			res += 1LL * p[0][i][x][1];
			x = p[0][i][x][0];
		}
	}
	if (f[x] <= f[y] && res >= d) return 1;
	res = 0, x = x1;
	d = (x - y + n) % n;
	for (long long i = LOG - 1; i >= 0; i--)
	{
		if (f[p[1][i][x][0]] <= f[y]) 
		{
			res += 1LL * p[1][i][x][1];
			x = p[1][i][x][0];
		}
	}
	return (f[x] <= f[y] && res >= d);
}

int compare_plants(int x, int y) 
{
	// ? x < y
	if (check(x, y)) return -1;
	if (check(y, x)) return 1;
	return 0;
	// return (a[x] > a[y] ? 1 : -1);
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25