Submission #303163

#	Time	Username	Problem	Language	Result	Execution time	Memory
303163		tutis	Comparing Plants (IOI20_plants)	C++17	32 / 100	1646 ms	49032 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>k0, k1;
int K, n;
vector<int>A;
struct ST
{
	int l, r;
	pair<int, int> mn;
	pair<int, int> mn1;
	int del = 0;
	int del1 = 0;
	ST *left, *right;
	ST(int l, int r, vector<int>&a): l(l), r(r)
	{
		if (l < r)
		{
			left = new ST(l, (l + r) / 2, a);
			right = new ST((l + r) / 2 + 1, r, a);
			mn = min(left->mn, right->mn);
		}
		else
			mn = {a[l], l};
		mn1 = mn;
	}
	void fix()
	{
		if (l == r)
		{
			mn.first += del;
			del = 0;
		}
		else
		{
			mn.first += del;
			left->del += del;
			right->del += del;
			del = 0;
		}
	}
	void fix1()
	{
		if (l == r)
		{
			mn1.first += del1;
			del1 = 0;
		}
		else
		{
			mn1.first += del1;
			left->del1 += del1;
			right->del1 += del1;
			del1 = 0;
		}
	}
	void add(int x, int y, int w)
	{
		if (x <= l && r <= y)
		{
			del += w;
			return fix();
		}
		fix();
		if (r < x || y < l)
			return;
		left->add(x, y, w);
		right->add(x, y, w);
		mn = min(left->mn, right->mn);
	}
	void add1(int x, int y, int w)
	{
		if (x <= l && r <= y)
		{
			del1 += w;
			return fix1();
		}
		fix1();
		if (r < x || y < l)
			return;
		left->add1(x, y, w);
		right->add1(x, y, w);
		mn1 = min(left->mn1, right->mn1);
	}
};
int id[200000];
int N;
struct inter
{
	int a, b;
	inter() {}
	inter(int x, int y)
	{
		a = x;
		b = y;
	}
	bool contains(int c)
	{
		if (a == -1 || b == -1)
			return false;
		if (a <= c && c <= b)
			return true;
		if (a > b)
			if (c >= a || c <= b)
				return true;
		return false;
	}
};
inter merge(inter a, inter b)
{
	if (a.a == -1)
		return b;
	if (b.a == -1)
		return a;
	if (a.a <= a.b && b.a <= b.b)
	{
		if (a.a == 0 && b.b == n - 1)
		{
			if (b.a > a.b)
				return inter(b.a, a.b);
			else
				return inter(1, 0);
		}
		return inter({min(a.a, b.a), max(a.b, b.b)});
	}
	if (a.a < a.b && b.a < b.b)
	{
		int x = min(a.a, b.a);
		int y = max(a.b, b.b);
		if (x <= y) return inter(1, 0);
		return inter(x, y);
	}
	if (a.a < a.b)
	{
		if (b.contains(a.a) || b.contains(a.a - 1))
		{
			int x = min(a.a, b.a);
			if (x <= a.b)
				return inter(1, 0);
			return inter(x, a.b);
		}
		else
		{
			int y = max(a.b, b.b);
			if (a.a <= y)
				return inter(1, 0);
			return inter(a.a, y);
		}
	}
}
struct ST1
{
	int l, r;
	inter xx;
	ST1 *left, *right;
	ST1(int l, int r): l(l), r(r)
	{
		if (l < r)
		{
			left = new ST1(l, (l + r) / 2);
			right = new ST1((l + r) / 2 + 1, r);
		}
		xx = inter(l, r);
	}
	void set(int i, inter g)
	{
		if (l == r)
		{
			xx = g;
		}
		else
		{
			if (i <= (l + r) / 2)
				left->set(i, g);
			else
				right->set(i, g);
			xx = merge(left->xx, right->xx);
		}
	}
	inter get(int x, int y)
	{
		if (x <= l && r <= y)
			return xx;
		if (y < l || r < x)
			return inter(-1, -1);
		return merge(left->get(x, y), right->get(x, y));
	}
} mediss(0, 200000);
inter gett(int x, int y)
{
	while (y >= n)
	{
		x -= n;
		y -= n;
	}
	while (x < 0)
	{
		x += n;
		y += n;
	}
	if (y < n)
	{
		return mediss.get(x, y);
	}
	else
	{
		return merge(mediss.get(x, n - 1), mediss.get(0, y - n));
	}
}
void init(int k, vector<int> r)
{
	K = k;
	n = r.size();
	N = n;
	if (k == 2)
	{
		k0 = k1 = vector<int>(n, 0);
		for (int t = 0; t < 2; t++)
			for (int i = n - 1; i >= 0; i--)
			{
				if (r[i] == 0)
					k0[i] = 1 + k0[(i + 1) % n];
				else
					k1[i] = 1 + k1[(i + 1) % n];
			}
		return;
	}
	if (2 * k > n)
	{
		ST medis(0, n - 1, r);
		auto add = [&](int x, int y, int w)
		{
			while (y >= n)
			{
				x -= n;
				y -= n;
			}
			while (x < 0)
			{
				x += n;
				y += n;
			}
			if (y < n)
			{
				medis.add(x, y, w);
			}
			else
			{
				medis.add(x, n - 1, w);
				medis.add(0, y - n, w);
			}
		};
		auto add1 = [&](int x, int y, int w)
		{
			while (y >= n)
			{
				x -= n;
				y -= n;
			}
			while (x < 0)
			{
				x += n;
				y += n;
			}
			if (y < n)
			{
				medis.add1(x, y, w);
			}
			else
			{
				medis.add1(x, n - 1, w);
				medis.add1(0, y - n, w);
			}
		};
		while (medis.mn1.first == 0)
		{
			int i = medis.mn1.second;
			add(i + 1, i + (k - 1), 1);
			add1(i, i, 1);
		}
		A = vector<int>(n, -1);
		for (int tt = 0; tt < n; tt++)
		{
			while (medis.mn1.first == 0)
			{
				int i = medis.mn1.second;
				add(i + 1, i + (k - 1), 1);
				add1(i, i, 1);
			}
			int i = medis.mn.second;
			add(i + 1, i + (k - 1), -1);
			add(i - (k - 1), i - 1, -1);
			add1(i - (k - 1), i - 1, -1);
			A[i] = tt;
			add(i, i, n + 10000);
			add1(i, i, n + 10000);
			r[i] = n + 100;
		}
		return;
	}
	ST medis(0, n - 1, r);
	auto add = [&](int x, int y, int w)
	{
		while (y >= n)
		{
			x -= n;
			y -= n;
		}
		while (x < 0)
		{
			x += n;
			y += n;
		}
		if (y < n)
		{
			medis.add(x, y, w);
		}
		else
		{
			medis.add(x, n - 1, w);
			medis.add(0, y - n, w);
		}
	};
	auto add1 = [&](int x, int y, int w)
	{
		while (y >= n)
		{
			x -= n;
			y -= n;
		}
		while (x < 0)
		{
			x += n;
			y += n;
		}
		if (y < n)
		{
			medis.add1(x, y, w);
		}
		else
		{
			medis.add1(x, n - 1, w);
			medis.add1(0, y - n, w);
		}
	};
	while (medis.mn1.first == 0)
	{
		int i = medis.mn1.second;
		add(i + 1, i + (k - 1), 1);
		add1(i, i, 1);
	}
	vector<int>K;
	for (int tt = 0; tt < n; tt++)
	{
		while (medis.mn1.first == 0)
		{
			int i = medis.mn1.second;
			add(i + 1, i + (k - 1), 1);
			add1(i, i, 1);
		}
		int i = medis.mn.second;
		add(i + 1, i + (k - 1), -1);
		add(i - (k - 1), i - 1, -1);
		add1(i - (k - 1), i - 1, -1);
		add(i, i, n + 10000);
		add1(i, i, n + 10000);
		id[i] = tt;
		K.push_back(i);
		r[i] = n + 100;
	}
	reverse(K.begin(), K.end());
	vector<int>ok;
	for (int i : K)
	{
		mediss.set(i, gett(i - (k - 1), i + (k - 1)));
	}
}

int compare_plants(int x, int y)
{
	assert(x < y);
	if (K == 2)
	{
		if (k0[x] >= y - x)
			return 1;
		if (k1[x] >= y - x)
			return -1;
		if (k0[y] >= n - y + x)
			return -1;
		if (k1[y] >= n - y + x)
			return 1;
		return 0;
	}
	if (!A.empty())
	{
		if (A[x] < A[y])
			return 1;
		else
			return -1;
	}
	if (id[x] > id[y])
		return -compare_plants(y, x);
	if (mediss.get(x, x).contains(y))
		return -1;
	return 0;
}

Compilation message (stderr)

plants.cpp: In function 'inter merge(inter, inter)':
plants.cpp:150:1: warning: control reaches end of non-void function [-Wreturn-type]
  150 | }
      | ^

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