Submission #607086

#	Time	Username	Problem	Language	Result	Execution time	Memory
607086		Temmie	Comparing Plants (IOI20_plants)	C++17	0 / 100	1 ms	424 KiB

plants

#include <bits/stdc++.h>

struct Seg {
	
	int size;
	std::vector <int> lazy, min;
	
	Seg(const std::vector <int> a) {
		size = 1;
		while (size < (int) a.size()) {
			size <<= 1;
		}
		lazy.resize(size << 1, 0);
		min.resize(size << 1, 1 << 30);
		build(a);
	}
	
	inline void push(int now, int l, int r) {
		min[now] += lazy[now];
		if (r - l - 1) {
			lazy[now * 2 + 1] += lazy[now];
			lazy[now * 2 + 2] += lazy[now];
		}
		lazy[now] = 0;
	}
	
	inline void build(const std::vector <int>& a) {
		build(a, 0, 0, a.size());
	}
	
	void build(const std::vector <int>& a, int now, int l, int r) {
		if (!(r - l - 1)) {
			min[now] = a[l];
			return;
		}
		int mid = (l + r) >> 1;
		build(a, now * 2 + 1, l, mid);
		build(a, now * 2 + 2, mid, r);
		min[now] = std::min(min[now * 2 + 1], min[now * 2 + 2]);
	}
	
	inline void update(int l, int r, int val) {
		update(l, r, val, 0, 0, size);
	}
	
	void update(int tl, int tr, int val, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return;
		}
		if (l >= tl && r <= tr) {
			lazy[now] += val;
			push(now, l, r);
			return;
		}
		int mid = (l + r) >> 1;
		push(now, l, r);
		update(tl, tr, val, now * 2 + 1, l, mid);
		update(tl, tr, val, now * 2 + 2, mid, r);
		min[now] = std::min(min[now * 2 + 1], min[now * 2 + 2]);
	}
	
	inline int find_last_zero(int l, int r) {
		if (l == r) {
			return -1;
		}
		return find_last_zero(l, r, 0, 0, size);
	}
	
	int find_last_zero(int tl, int tr, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return -1;
		}
		push(now, l, r);
		if (min[now]) {
			return -1;
		}
		if (!(r - l - 1)) {
			return l;
		}
		int mid = (l + r) >> 1;
		int right = find_last_zero(tl, tr, now * 2 + 2, mid, r);
		return right == -1 ? find_last_zero(tl, tr, now * 2 + 1, l, mid) : right;
	}
	
	inline int find_first_zero(int l, int r) {
		if (l == r) {
			return -1;
		}
		return find_first_zero(l, r, 0, 0, size);
	}
	
	int find_first_zero(int tl, int tr, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return -1;
		}
		push(now, l, r);
		if (min[now]) {
			return -1;
		}
		if (!(r - l - 1)) {
			return l;
		}
		int mid = (l + r) >> 1;
		int left = find_first_zero(tl, tr, now * 2 + 1, l, mid);
		return left == -1 ? find_first_zero(tl, tr, now * 2 + 2, mid, r) : left;
	}
	
	inline int query(int ind) {
		return query(ind, 0, 0, size);
	}
	
	int query(int ind, int now, int l, int r) {
		push(now, l, r);
		if (!(r - l - 1)) {
			return min[now];
		}
		int mid = (l + r) >> 1;
		return ind < mid ? query(ind, now * 2 + 1, l, mid) : query(ind, now * 2 + 2, mid, r);
	}
	
	inline int query(int l, int r) {
		return query(l, r, 0, 0, size);
	}
	
	int query(int tl, int tr, int now, int l, int r) {
		if (l >= tr || r <= tl) {
			return 1 << 30;
		}
		push(now, l, r);
		if (l >= tl && r <= tr) {
			return min[now];
		}
		int mid = (l + r) >> 1;
		return std::min(query(tl, tr, now * 2 + 1, l, mid), query(tl, tr, now * 2 + 2, mid, r));
	}
	
	inline void set(int ind, int val) {
		set(ind, val, 0, 0, size);
	}
	
	void set(int ind, int val, int now, int l, int r) {
		if (!(r - l - 1)) {
			lazy[now] = 0;
			min[now] = val;
			return;
		}
		int mid = (l + r) >> 1;
		push(now, l, r);
		ind < mid ? set(ind, val, now * 2 + 1, l, mid) : set(ind, val, now * 2 + 2, mid, r);
		push(now * 2 + 1, l, mid);
		push(now * 2 + 2, mid, r);
		min[now] = std::min(min[now * 2 + 1], min[now * 2 + 2]);
	}
	
};

int n, k;
std::vector <int> h;
std::vector <std::vector <int>> bin_left, bin_right;

void init(int _k, std::vector <int> r) {
	n = r.size();
	k = _k;
	h.resize(n, -1);
	Seg seg(r);
	std::vector <int> ord;
	auto f = [&] (auto&& self, int node) -> void {
		int ind = -1;
		do {
			ind = -1;
			if (node - k + 1 >= 0) {
				ind = seg.find_last_zero(node - k + 1, node);
			} else {
				ind = seg.find_last_zero(0, node);
				if (ind == -1) {
					ind = seg.find_first_zero(n - ((k - 1) - node), n);
				}
			}
			if (ind != -1) {
				self(self, ind);
			}
		} while (ind != -1);
		if (node - k + 1 >= 0) {
			seg.update(node - k + 1, node + 1, -1);
		} else {
			seg.update(0, node + 1, -1);
			seg.update(n - ((k - 1) - node), n, -1);
		}
		seg.update(node, node + 1, 1 << 30);
		ord.push_back(node);
	};
	while (true) {
		int v = seg.find_first_zero(0, n);
		if (v == -1) {
			break;
		}
		f(f, v);
	}
	assert((int) ord.size() == n);
	for (int i = 0; i < n; i++) {
		h[ord[i]] = n - i - 1;
	}
	std::vector <int> left(n, -1), right(n - 1);
	Seg fseg(std::vector <int> (n, 1 << 30));
	for (int i = n - 1; i >= 0; i--) {
		int node = ord[i];
		if (node - k + 1 >= 0) {
			int val = fseg.query(node - k + 1, node);
			left[node] = val < (1 << 30) ? ord[val] : -1;
		} else {
			int val = std::min(fseg.query(0, node), fseg.query(n - ((k - 1) - node), n));
			left[node] = val < (1 << 30) ? ord[val] : -1;
		}
		if (node + k - 1 < n) {
			int val = fseg.query(node + 1, node + k);
			right[node] = val < (1 << 30) ? ord[val] : -1;
		} else {
			int val = std::min(fseg.query(node + 1, n), fseg.query(0, (k - 1) - (n - node - 1)));
			right[node] = val < (1 << 30) ? ord[val] : -1;
		}
		fseg.set(node, i);
	}
	bin_left.resize(20, std::vector <int> (n, -1));
	bin_right.resize(20, std::vector <int> (n, -1));
	bin_left[0] = left;
	bin_right[0] = right;
	for (int b = 1; b < 20; b++) {
		for (int i = 0; i < n; i++) {
			bin_left[b][i] = bin_left[b - 1][i] == -1 ? -1 : bin_left[b - 1][bin_left[b - 1][i]];
			bin_right[b][i] = bin_right[b - 1][i] == -1 ? -1 : bin_right[b - 1][bin_right[b - 1][i]];
		}
	}
}

inline bool contains(int from, int to, int target) {
	if (from <= to) {
		return from <= target && target <= to;
	}
	return contains(from, n - 1, target) || contains(0, to, target);
}

inline int dist(int from, int to) {
	if (from <= to) {
		return to - from;
	}
	return to + 1 + (n - from - 1);
}

bool greater(int u, int v) {
	{
		int ind = u;
		int d = dist(v, u) - 1;
		for (int b = 19; b >= 0; b--) {
			if (bin_left[b][ind] != -1 && d - dist(bin_left[b][ind], ind) >= 0) {
				ind = bin_left[b][ind];
				d -= dist(bin_left[b][ind], ind);
			}
		}
		int v1 = ind;
		int v2 = bin_left[0][ind];
		if (v2 != -1 && contains(v2, v1, v) && h[v1] > h[v]) {
			return true;
		}
	}
	{
		int ind = u;
		int d = dist(u, v) - 1;
		for (int b = 19; b >= 0; b--) {
			if (bin_right[b][ind] != -1 && d - dist(ind, bin_right[b][ind]) >= 0) {
				ind = bin_right[b][ind];
				d -= dist(ind, bin_right[b][ind]);
			}
		}
		int v1 = ind;
		int v2 = bin_right[0][ind];
		if (v2 != -1 && contains(v1, v2, v) && h[v1] > h[v]) {
			return true;
		}
	}
	return false;
}

int compare_plants(int u, int v) {
	if (greater(u, v)) {
		return 1;
	}
	if (greater(v, u)) {
		return -1;
	}
	return 0;
}

• 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