Submission #303201

#	Time	Username	Problem	Language	Result	Execution time	Memory
303201		tutis	Comparing Plants (IOI20_plants)	C++17	11 / 100	4089 ms	219092 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
{
	set<int>A;
	inter() {}
	void add(int i)
	{
		A.insert(i);
	}
	bool contains(int c)
	{
		if (A.count(c))
			return true;
		return false;
	}
};
inter merge(const inter &a, const inter &b)
{
	inter c = a;
	for (int t : b.A)
		c.add(t);
	return c;
}
struct ST1
{
	int l, r;
	inter lazy;
	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);
		}
	}
	void fix()
	{
		if (l < r)
		{
			left->lazy = merge(left->lazy, lazy);
			right->lazy = merge(right->lazy, lazy);
			lazy = inter();
		}
	}
	void add(int x, int y, inter g)
	{
		if (x <= l && r <= y)
		{
			lazy = merge(lazy, g);
			return fix();
		}
		fix();
		if (y < l || r < x)
			return;
		left->add(x, y, g);
		right->add(x, y, g);
	}
	inter get(int x)
	{
		if (l == r)
			return lazy;
		fix();
		if (x <= (l + r) / 2)
			return left->get(x);
		else
			return right->get(x);
	}
} mediss(0, 200000);
void adddd(int x, int y, inter c)
{
	while (y >= n)
	{
		x -= n;
		y -= n;
	}
	while (x < 0)
	{
		x += n;
		y += n;
	}
	if (y < n)
	{
		return mediss.add(x, y, c);
	}
	else
	{
		mediss.add(x, n - 1, c);
		mediss.add(0, y - n, c);
	}
}
inter C[200000];
void init(int k, vector<int> r)
{
	K = k;
	n = r.size();
	N = 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);
	}
	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)
	{
		inter c = mediss.get(i);
		c.add(i);
		C[i] = c;
		adddd(i - (k - 1), i + (k - 1), c);
	}
}

int compare_plants(int x, int y)
{
	if (C[x].contains(y))
		return 1;
	if (C[y].contains(x))
		return -1;
	return 0;
}

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