Submission #1205229

#	Time	Username	Problem	Language	Result	Execution time	Memory
1205229		bangan	Comparing Plants (IOI20_plants)	C++20	15 / 100	738 ms	43256 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

struct Node {
	int pos, val;
	Node(int pos_ = 0, int val_ = 0): pos(pos_), val(val_) {}

	Node friend operator+ (Node a, Node b) {
		if (a.val == b.val) {
			return a.pos < b.pos ? a : b;
		} else {
			return a.val < b.val ? a : b;
		}
	}
};

struct SegmentTree {
	#define lc (v << 1)
	#define rc (v << 1 | 1)
	#define mid (l + r) / 2

	int n;
	std::vector<Node> a;
	std::vector<int> b;
	SegmentTree(int n_): n(n_), a(4 * n + 1), b(4 * n + 1, 0) {}

	void push(int v) {
		if (a[v].val != n) {
			a[v].val += b[v];
		}
		if (lc <= 4 * n) {
			b[lc] += b[v];
		}
		if (rc <= 4 * n) {
			b[rc] += b[v];
		}
		b[v] = 0;
	}

	void set_val(int i, int x, int v, int l, int r) {
		push(v);
		if (r - l == 1) {
			a[v] = Node(i, x);
			return;
		}

		i < mid ? set_val(i, x, lc, l, mid) : set_val(i, x, rc, mid, r);

		push(lc);
		push(rc);
		a[v] = a[lc] + a[rc];
	}
	void set_val(int i, int x) {
		set_val(i, x, 1, 0, n);
	}

	void update(int s, int e, int x, int v, int l, int r) {
		push(v);
		if (s <= l && r <= e) {
			b[v] += x;
			push(v);
			return;
		}

		if (s < mid) {
			update(s, e, x, lc, l, mid);
		}
		if (e > mid) {
			update(s, e, x, rc, mid, r);
		}

		push(lc);
		push(rc);
		a[v] = a[lc] + a[rc];
	}
	void update(int s, int e, int x) {
		update(s, e, x, 1, 0, n);
	};

	Node get(int s, int e, int v, int l, int r) {
		push(v);
		if (s <= l && r <= e) {
			return a[v];
		}

		if (e <= mid) {
			return get(s, e, lc, l, mid);
		} else if (s >= mid) {
			return get(s, e, rc, mid, r);
		} else {
			return get(s, e, lc, l, mid) + get(s, e, rc, mid, r);
		}
	}
	Node get(int s, int e) {
		return get(s, e, 1, 0, n);
	}
};

constexpr int N = 2E5;

int n, h[N];
std::bitset<N> less, more;

void init(int k, std::vector<int> org_r) {
	n = org_r.size();

	auto norm = [&](int i) {
		i %= n;
		if (i < 0) {
			return i + n;
		} else {
			return i;
		}
	};

	SegmentTree r(n);
	for (int i = 0; i < n; i++) {
		r.set_val(i, org_r[i]);
	}
	auto get = [&](int s, int e) -> Node {
		s = norm(s);
		e = norm(e);
		// std::cout << "(s, e) = (" << s << ", " << e << ")\n";
		if (s <= e) {
			return r.get(s, e + 1);
		} else {
			return r.get(s, n) + r.get(0, e + 1);
		}
	};
	auto update = [&](int s, int e, int x) {
		s = norm(s);
		e = norm(e);
		if (s <= e) {
			r.update(s, e + 1, x);
		} else {
			r.update(s, n, x);
			r.update(0, e + 1, x);
		}
	};

	std::vector<int> ord;
	auto dec = [&](auto self, int i) -> void {
		while (get(i - k + 1, i - 1).val == 0) {
			self(self, get(i - k + 1, i - 1).pos);
		}

		ord.push_back(i);
		r.set_val(i, n);
		update(i - k + 1, i - 1, -1);
	};
	while (get(0, n - 1).val < n) {
		int i = get(0, n - 1).pos;
		dec(dec, i);
	}
	for (int i = 0; i < n; i++) {
		h[ord[i]] = n - i - 1;
	}

	auto cmp = [&](int i, int j) {
		return h[i] < h[j];
	};
	std::set<int, decltype(cmp)> cur(cmp);

	for (int i = 0; i < k; i++) {
		cur.insert(i);
	}

	std::vector<std::vector<int>> in(n), out(n);
	for (int s = 0, e = k - 1; s < n; s++, e = norm(e + 1)) {
		{
			auto it = cur.find(s);
			if (std::next(it) != cur.end()) {
				in[s].push_back(*std::next(it));
			}
			if (it != cur.begin()) {
				out[s].push_back(*std::prev(it));
			}
		} 

		{
			auto it = cur.find(e);
			if (std::next(it) != cur.end()) {
				in[e].push_back(*std::next(it));
			}
			if (it != cur.begin()) {
				out[e].push_back(*std::prev(it));
			}
		}

		{
			cur.erase(s);
			cur.insert(norm(e + 1));
		}
	}

	auto dfs_in = [&](auto self, int v) -> void {
		more[v] = true;
		for (int u : in[v]) {
			if (!more[u]) {
				self(self, u);
			}
		}
	};
	auto dfs_out = [&](auto self, int v) -> void {
		less[v] = true;
		for (int u : out[v]) {
			if (!less[u]) {
				self(self, u);
			}
		}
	};

	dfs_in(dfs_in, 0);
	dfs_out(dfs_out, 0);
}

int compare_plants(int x, int y) {
	assert(x == 0);
	if (less[y] == more[y]) {
		return 0;
	} else if (less[y]) {
		return 1;
	} else {
		return -1;
	}
}

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