Submission #425695

#	Time	Username	Problem	Language	Result	Execution time	Memory
425695		Mlxa	Comparing Plants (IOI20_plants)	C++14	100 / 100	1985 ms	62312 KiB

plants

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "plants.h"
#define cerr if (0) cout

namespace my {

const int L = 18;
const int N = 1 << L;
int n, k, kth[N], can[N];

struct tree_t {
	pair<int, int> mi[2 * N];
	int pu[2 * N];
	int ls(int v) {
		return 2 * v + 1;
	}
	int rs(int v) {
		return 2 * v + 2;
	}
	void build(int v, int l, int r) {
		if (r - l == 1) {
			mi[v] = mp(kth[l], l);
		} else {
			int m = (l + r) / 2;
			build(ls(v), l, m);
			build(rs(v), m, r);
			mi[v] = min(mi[ls(v)], mi[rs(v)]);
		}
	}
	void build() {
		build(0, 0, N);
	}
	void push(int v) {
		mi[ls(v)].x += pu[v];
		mi[rs(v)].x += pu[v];
		pu[ls(v)] += pu[v];
		pu[rs(v)] += pu[v];
		pu[v] = 0;
	}
	void upd(int v, int vl, int vr, int ql, int qr, int d) {
		if (ql <= vl && vr <= qr) {
			mi[v].x += d;
			pu[v] += d;
			return;
		}
		if (qr <= vl || vr <= ql) {
			return;
		}
		push(v);
		int vm = (vl + vr) / 2;
		upd(ls(v), vl, vm, ql, qr, d);
		upd(rs(v), vm, vr, ql, qr, d);
		mi[v] = min(mi[ls(v)], mi[rs(v)]);
	}
	void range_add(int l, int r, int value) {
		upd(0, 0, N, l, r, value);
	}
	void cycle_add(int from, int value) {
		from %= n; from += n; from %= n;
		if (from + k <= n) {
			range_add(from, from + k, value);
		} else {
			range_add(from, n, value), range_add(0, from + k - n, value);
		}
	}
	pair<int, int> query(int v, int vl, int vr, int ql, int qr) {
		if (ql <= vl && vr <= qr) {
			return mi[v];
		}
		if (qr <= vl || vr <= ql) {
			return mp(N, -1);
		}
		int vm = (vl + vr) / 2;
		push(v);
		return min(query(ls(v), vl, vm, ql, qr), query(rs(v), vm, vr, ql, qr));
	}
	pair<int, int> range_min(int l, int r) {
		return query(0, 0, N, l, r);
	}
	pair<int, int> cycle_min(int from) {
		from %= n; from += n; from %= n;
		if (from + k <= n) {
			return range_min(from, from + k);
		} else {
			return min(range_min(from, n), range_min(0, from + k - n));
		}
	}
} tree;

vector<int> topsort;

void extract(int v) {
	tree.range_add(v, v + 1, N);
	while (1) {
		auto e = tree.cycle_min(v - k + 1);
		if (e.x) break;
		extract(e.y);
	}
	tree.cycle_add(v - k + 1, -1);
	topsort.push_back(v);
}

const int BAD = -1;
int lef[L][N], rig[L][N];
}

bool btw(int l, int r, int w) {
	if (l <= r) {
		return l <= w && w <= r;
	} else {
		return l <= w || w <= r;
	}
}

void init(int _k, vector<int> _r) {
	using namespace my;
	n = (int)_r.size();
	k = _k;
	copy(all(_r), kth);
	tree.build();
	while (1) {
		auto e = tree.range_min(0, n);
		if (e.x) break;
		extract(e.y);
	}
	assert((int)topsort.size() == n);
	reverse(all(topsort));
	for (int i = 0; i < n; ++i) {
		can[topsort[i]] = i;
	}
	set<pair<int, int>> iset;
	for (int i = 0; i < k - 1; ++i) {
		iset.emplace(can[i], i);
	}
	fill_n(lef[0], L * N, BAD), fill_n(rig[0], L * N, BAD);
	for (int i = k - 1;;) {
		auto it = iset.lower_bound(mp(can[i], i));
		if (it != iset.begin()) {
			--it;
			lef[0][i] = it->y;
		}
		iset.erase({can[(i + n - k + 1) % n], (i + n - k + 1) % n});
		iset.emplace(can[i], i);
		(i += 1) %= n;
		if (i == k - 1) break;
	}
	iset.clear();
	for (int i = 0; i < k - 1; ++i) {
		iset.emplace(can[i], i);
	}
	for (int i = n - 1; i >= 0; --i) {
		auto it = iset.lower_bound(mp(can[i], i));
		if (it != iset.begin()) {
			--it;
			rig[0][i] = it->y;
		}
		iset.erase({can[(i + k - 1) % n], (i + k - 1) % n});
		iset.emplace(can[i], i);
	}
	for (int i = 0; i < n; ++i) {
		cerr << i << " " << lef[0][i] << " " << rig[0][i] << endl;
	}
	for (int i = 0; i < n; ++i) {
		cerr << can[i] << " ";
	}
	cerr << endl;
	for (int it = 1; it < L; ++it) {
		for (int i = 0; i < n; ++i) {
			if (lef[it - 1][i] != BAD) {
				int j = lef[it - 1][i];
				if (j == BAD || btw(lef[it - 1][j], j, i)) {
					continue;
				}
				lef[it][i] = lef[it - 1][j];
			}
		}
	}
	for (int it = 1; it < L; ++it) {
		for (int i = 0; i < n; ++i) {
			if (rig[it - 1][i] != BAD) {
				int j = rig[it - 1][i];
				if (j == BAD || btw(j, rig[it - 1][j], i)) {
					continue;
				}
				rig[it][i] = rig[it - 1][j];
			}
		}
	}
}

bool taller(int x, int y) {
	using namespace my;
	cerr << "taller " << x << " " << y << endl;
	int z = x;
	for (int it = L - 1; it >= 0; --it) {
		int v = lef[it][z];
		cerr << it << " " << z << " " << v << endl;
		if (v == BAD || btw(v, z, y)) {
			continue;
		}
		z = v;
	}
	cerr << "z = " << z << " " << y << endl;
	assert(lef[0][z] == BAD || btw(lef[0][z], z, y));
	if (lef[0][z] != BAD && btw(lef[0][z], z, y) && can[z] >= can[y]) {
		return true;
	}
	z = x;
	for (int it = L - 1; it >= 0; --it) {
		int v = rig[it][z];
		if (v == BAD || btw(z, v, y)) {
			continue;
		}
		z = v;
	}
	assert(rig[0][z] == BAD || btw(z, rig[0][z], y));
	cerr << "z = " << z << endl;
	if (rig[0][z] != BAD && btw(z, rig[0][z], y) && can[z] >= can[y]) {
		return true;
	}
	return false;
}

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

#ifdef LC
#include "grader.cpp"
#endif

• 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