Submission #811193

#	Time	Username	Problem	Language	Result	Execution time	Memory
811193		LittleCube	Comparing Plants (IOI20_plants)	C++17	100 / 100	1470 ms	115252 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define ll long long
using namespace std;

namespace
{
	int n, k, order[200005], out[200005], in[200005];
	ll l[200005][20], r[200005][20];
}

struct segTree
{
	pll seg[800005];
	ll lazy[800005];

	void init(int i = 1, int L = 0, int R = n - 1)
	{
		seg[i].S = L;
		if (L == R)
			return;
		int mid = (L + R) / 2;
		init(i << 1, L, mid);
		init(i << 1 | 1, mid + 1, R);
	}

	void modify(int mL, int mR, ll val, int i = 1, int L = 0, int R = n - 1)
	{
		if (mL <= L && R <= mR)
		{
			lazy[i] += val;
			seg[i].F += val;
		}
		else if (R < mL || mR < L)
			return;
		else
		{
			int mid = (L + R) / 2;
			lazy[i << 1] += lazy[i];
			lazy[i << 1 | 1] += lazy[i];
			seg[i << 1].F += lazy[i];
			seg[i << 1 | 1].F += lazy[i];
			lazy[i] = 0;
			modify(mL, mR, val, i << 1, L, mid);
			modify(mL, mR, val, i << 1 | 1, mid + 1, R);
			seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
		}
	}

	pll query(int qL, int qR, int i = 1, int L = 0, int R = n - 1)
	{
		if (qL <= L && R <= qR)
			return seg[i];
		else if (R < qL || qR < L)
			return pll(1e9, n + 1);
		else
		{
			int mid = (L + R) / 2;
			lazy[i << 1] += lazy[i];
			lazy[i << 1 | 1] += lazy[i];
			seg[i << 1].F += lazy[i];
			seg[i << 1 | 1].F += lazy[i];
			lazy[i] = 0;
			return min(query(qL, qR, i << 1, L, mid),
					   query(qL, qR, i << 1 | 1, mid + 1, R));
		}
	}
	void safe_modify(int l, int r, ll val)
	{
		if (l <= r)
			modify(l, r, val);
		else
		{
			modify(l, n - 1, val);
			modify(0, r, val);
		}
	}
} seg, zero;

struct changeValseg
{
	ll seg[800005];

	void init(int i = 1, int L = 0, int R = n - 1)
	{
		seg[i] = -1;
		if (L == R)
			return;
		int mid = (L + R) / 2;
		init(i << 1, L, mid);
		init(i << 1 | 1, mid + 1, R);
	}

	void modify(int mL, int mR, ll val, int i = 1, int L = 0, int R = n - 1)
	{
		if (mL <= L && R <= mR)
			seg[i] = val;
		else if (R < mL || mR < L)
			return;
		else
		{
			if (seg[i] != -1)
			{
				seg[i << 1] = seg[i << 1 | 1] = seg[i];
				seg[i] = -1;
			}
			int mid = (L + R) / 2;
			modify(mL, mR, val, i << 1, L, mid);
			modify(mL, mR, val, i << 1 | 1, mid + 1, R);
		}
	}

	ll query(int pos, int i = 1, int L = 0, int R = n - 1)
	{
		if (seg[i] != -1 || L == R)
			return seg[i];
		else
		{
			int mid = (L + R) / 2;
			if (pos <= mid)
				return query(pos, i << 1, L, mid);
			else
				return query(pos, i << 1 | 1, mid + 1, R);
		}
	}

	void safe_modify(int l, int r, ll val)
	{
		if (l <= r)
			modify(l, r, val);
		else
		{
			modify(l, n - 1, val);
			modify(0, r, val);
		}
	}
} open, conceal;

const ll inf = 1e9;

void init(int k, vector<int> r)
{
	n = r.size();
	::k = k;
	seg.init();
	zero.init();
	open.init();
	conceal.init();
	for (int i = 0; i < n; i++)
	{
		r[i] = k - 1 - r[i];
		seg.modify(i, i, r[i]);
		zero.modify(i, i, r[i]);
	}
	for (int it = 1; it <= n; it++)
	{
		{
			auto [v, p] = zero.query(0, n - 1);
			while (v == 0)
			{
				seg.safe_modify((p + 1) % n, (p + k - 1) % n, inf);
				zero.modify(p, p, inf);
				out[p] = open.query(p);
				tie(v, p) = zero.query(0, n - 1);
			}
		}
		int cur = seg.query(0, n - 1).S;
		in[cur] = conceal.query(cur);
		// cerr << cur << "->" << in[cur] << ' ' << out[cur] << '\n';
		seg.modify(cur, cur, inf);
		seg.safe_modify((cur + 1) % n, (cur + k - 1) % n, -inf);
		zero.safe_modify((cur - k + 1 + n) % n, cur, -1);
		seg.safe_modify((cur - k + 1 + n) % n, cur, -1);
		conceal.safe_modify((cur + 1) % n, (cur + k - 1) % n, cur);
		open.safe_modify((cur - k + 1 + n) % n, cur, cur);
		assert(order[cur] == 0);
		order[cur] = it;
	}

	vector<int> ord(n);
	for (int i = 0; i < n; i++)
		ord[order[i] - 1] = i;
	for (int i = 0; i < n; i++)
	{
		int u = ord[i];
		if (in[u] >= 0)
			l[u][0] = (u - in[u] + n) % n;
		else
			l[u][0] = 0;
		if (out[u] >= 0)
			::r[u][0] = (out[u] - u + n) % n;
		else
			::r[u][0] = 0;
	}
	for (int p = 0; p + 1 < 20; p++)
		for (int i = 0; i < n; i++)
		{
			l[i][p + 1] = l[i][p] + l[((i - l[i][p]) % n + n) % n][p];
			::r[i][p + 1] = ::r[i][p] + ::r[(i + ::r[i][p]) % n][p];
		}
	// for (int i = 0; i < n; i++)
	// 	cerr << in[i] << ' ' << l[i] << ' ' << out[i] << ' ' << ::r[i] << '\n';
}

bool reach(int x, int y)
{
	// check left
	int u = x, v = y;
	if (u > v)
		u -= n;
	for (int p = 19; p >= 0; p--)
		if (u <= v - l[(v + n) % n][p])
			v = v - l[(v + n) % n][p];
	if (abs(u - v) < k && order[(u + n) % n] <= order[(v + n) % n])
		return 1;
	u = x, v = y;
	if (u < v)
		u += n;
	for (int p = 19; p >= 0; p--)
		if (v + r[v % n][p] <= u)
			v = v + r[v % n][p];
	if (abs(u - v) < k)
		return order[u % n] <= order[v % n];
	return 0;
}

int compare_plants(int x, int y)
{
	if (reach(x, y))
		return -1;
	if (reach(y, x))
		return 1;
	return 0;
}

• 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