Submission #769079

#	Time	Username	Problem	Language	Result	Execution time	Memory
769079		t6twotwo	Comparing Plants (IOI20_plants)	C++17	49 / 100	395 ms	32576 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, K;
vector<int> R, A, pfs;
int dis(int x, int y) {
	if (x < y) {
		return y - x;
	} else {
		return N - x + y;
	}
}
void init(int k, std::vector<int> r) {
	K = k, R = r; N = R.size();
	if (K == 2) {
		pfs.resize(N + 1);
		for (int i = 0; i < N; i++) {
			pfs[i + 1] = pfs[i] + R[i];
		}
		return;
	}
	A.resize(N, -1);
	int M = 2 << __lg(N - 1);
	vector<int> st(2 * M - 1), lazy(2 * M - 1);
	auto push = [&](int p) {
		st[p * 2 + 1] += lazy[p];
		st[p * 2 + 2] += lazy[p];
		lazy[p * 2 + 1] += lazy[p];
		lazy[p * 2 + 2] += lazy[p];
		lazy[p] = 0;
	};
	auto pull = [&](int p) {
		st[p] = max(st[p * 2 + 1], st[p * 2 + 2]);
	};
	for (int i = 0; i < N; i++) {
		st[i + M - 1] = R[i];
	}
	for (int i = M - 2; i >= 0; i--) {
		pull(i);
	}
	auto modify = [&](auto f, int p, int l, int r, int x, int v) -> void {
		if (r - l == 1) {
			st[p] = v;
			return;
		}
		int m = (l + r + 1) / 2;
		push(p);
		if (x < m) {
			f(f, p * 2 + 1, l, m, x, v);
		} else {
			f(f, p * 2 + 2, m, r, x, v);
		}
		pull(p);
	};
	auto update = [&](auto f, int p, int l, int r, int L, int R) -> void {
		if (R <= l || r <= L) {
			return;
		}
		if (L <= l && r <= R) {
			st[p]++;
			lazy[p]++;
			return;
		}
		int m = (l + r + 1) / 2;
		push(p);
		f(f, p * 2 + 1, l, m, L, R);
		f(f, p * 2 + 2, m, r, L, R);
		pull(p);
	};
	auto find = [&](auto f, int p, int l, int r) {
		if (r - l == 1) {
			return l;
		}
		int m = (l + r + 1) / 2;
		push(p);
		if (st[p * 2 + 1] == K - 1) {
			return f(f, p * 2 + 1, l, m);
		} else {
			return f(f, p * 2 + 2, m, r);
		}
	};
	set<pair<int, int>> s;
	set<int> cand;
	vector<int> d(N);
	for (int i = 0; i < N; i++) {
		while (st[0] == K - 1) {
			int x = find(find, 0, 0, M);
			modify(modify, 0, 0, M, x, -1e9);
			if (s.empty()) {
				s.emplace(d[x] = 1e9, x);
				cand.insert(x);
			} else {
				auto it = cand.lower_bound(x);
				int l, r;
				if (it == cand.end()) {
					r = *cand.begin();
					l = *prev(it);
				} else {
					r = *it;
					if (it == cand.begin()) {
						l = *prev(cand.end());
					} else {
						l = *prev(it);
					}
				}
				s.erase(s.find({d[r], r}));
				s.emplace(d[x] = dis(l, x), x);
				s.emplace(d[r] = dis(x, r), r);
				cand.insert(x);
			}
		}
		auto [t, x] = *prev(s.end());
		s.erase(prev(s.end()));
		cand.erase(x);
		if (!cand.empty()) {
			auto it = cand.lower_bound(x);
			int y;
			if (it == cand.end()) {
				y = *cand.begin();
			} else {
				y = *it;
			}
			s.erase({d[y], y});
			s.emplace(d[y] += d[x], y);
		}
		A[x] = i;
		if (x > 0) {
			update(update, 0, 0, M, max(0, x - (K - 1)), x);
		}
		if (x - (K - 1) < 0) {
			update(update, 0, 0, M, N + x - (K - 1), N);
		}
	}
}
 
int compare_plants(int x, int y) {
	if (K == 2) {
		if (pfs[y] - pfs[x] == 0) {
			return 1;
		}
		if (pfs[y] - pfs[x] == y - x) {
			return -1;
		}
		if (pfs[N] - pfs[y] + pfs[x] == 0) {
			return -1;
		}
		if (pfs[N] - pfs[y] + pfs[x] == N - 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: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25