Submission #813247

#	Time	Username	Problem	Language	Result	Execution time	Memory
813247		prvocislo	Comparing Plants (IOI20_plants)	C++17	0 / 100	31 ms	61936 KiB

plants

#include "plants.h"
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

const int maxn = 1 << 19, logn = 19, inf = 1e9 + 5;
vector<pair<int, int> > mini(maxn * 2, { inf, -1 });
vector<int> l(maxn * 2), r(maxn * 2), lz(maxn * 2, 0);
void add(int li, int ri, int x, int vr = 1)
{
	if (ri < l[vr] || r[vr] < li) return;
	if (li <= l[vr] && r[vr] <= ri) return lz[vr] += x, mini[vr].first += x, void();
	add(li, ri, x, (vr << 1)), add(li, ri, x, (vr << 1) | 1);
	mini[vr] = min(mini[vr << 1], mini[(vr << 1) | 1]), mini[vr].first += lz[vr];
}
int n, k;
pair<int, int> query(int li, int ri, int vr = 1)
{
	if (ri < l[vr] || r[vr] < li) return { inf, -1 };
	if (li <= l[vr] && r[vr] <= ri) return mini[vr];
	return min(query(li, ri, vr << 1), query(li, ri, (vr << 1) | 1));
}
vector<int> ord;
set<int> v0; set<pair<int, int> > ordv; // {vzdialenost od predoslej 0, pozicia}
pair<int, int> give_pair(int x)
{
	if (v0.empty()) return { n, x };
	if (x <= *v0.begin()) return { n + x - *prev(v0.end()), x };
	return { x - *prev(v0.lower_bound(x)), x };
}
void pridaj(int x)
{
	auto nx = v0.upper_bound(x);
	if (!v0.empty() && nx == v0.end()) nx = v0.begin();
	int val = (nx == v0.end() || *nx == x ? -1 : *nx);
	if (val != -1) ordv.erase(give_pair(val));
	v0.insert(x), ordv.insert(give_pair(x));
	if (val != -1) ordv.insert(give_pair(val));
}
void zober(int x)
{
	auto nx = v0.upper_bound(x);
	if (!v0.empty() && nx == v0.end()) nx = v0.begin();
	int val = (nx == v0.end() || *nx == x ? -1 : *nx);
	if (val != -1) ordv.erase(give_pair(val));
	ordv.erase(give_pair(x)), v0.erase(x);
	if (val != -1) ordv.insert(give_pair(val));
}
vector<vector<int> > hr(logn, vector<int>(maxn, 0));
void init(int K, vector<int> h)
{
	n = h.size(), k = K;
	ord.resize(n, -1);
	for (int i = 0; i < n; i++)
	{
		if (h[i]) mini[maxn + i] = { h[i], i };
		else pridaj(i);
	}
	for (int i = maxn; i < maxn * 2; i++) l[i] = r[i] = i - maxn;
	for (int i = maxn - 1; i; i--) l[i] = l[i * 2], r[i] = r[i * 2 + 1], mini[i] = min(mini[i * 2], mini[i * 2 + 1]);
	for (int i = n - 1; i >= 0; i--)
	{
		int id = prev(ordv.end())->second;
		ord[id] = i;
		zober(id);
		add(id - (k - 1), id - 1, -1), add(n + id - (k - 1), n - 1, -1);
		while (mini[1].first == 0)
		{
			int x = mini[1].second;
			add(x, x, inf), pridaj(x);
		}
	}
	vector<pair<int, int> > pr;
	for (int i = 0; i < 2 * n; i++) mini[maxn + i] = { ord[i % n], i }, pr.push_back({ ord[i % n], i });
	for (int i = maxn - 1; i; i--) mini[i] = min(mini[i << 1], mini[(i << 1) | 1]);
	sort(pr.begin(), pr.end());
	for (pair<int, int> pp : pr)
	{
		int i = pp.second;
		hr[0][i] = query(i + 1, i + k - 1).second;
		if (hr[0][i] == -1) hr[0][i] = i;
		add(i, i, inf);
	}
	for (int j = 1; j < logn; j++) for (int i = 0; i < 2 * n; i++) hr[j][i] = hr[j - 1][hr[j - 1][i]];
}
int higher(int x, int y) // je x urcite nizsie ako y -> plati x < y
{
	for (int j = logn - 1; j >= 0; j--) if (hr[j][x] <= y) x = hr[j][x];
	if (ord[x % n] <= ord[y % n] && abs(y - x) < k) return 1;
	return 0;
}
int compare_plants(int x, int y)
{
	return higher(y, x + n) - higher(x, y);
}

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