Submission #417153

#	Time	Username	Problem	Language	Result	Execution time	Memory
417153		KoD	Comparing Plants (IOI20_plants)	C++17	32 / 100	987 ms	19452 KiB

plants

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

template <class T> using Vec = std::vector<T>;

constexpr int INF = 1000000000;

struct Monoid {
	int min;
	explicit constexpr Monoid(const int m): min(m) {}
	static constexpr Monoid zero() {
		return Monoid(INF);
	}
	constexpr Monoid operator + (const Monoid& other) const {
		return Monoid(std::min(min, other.min));
	}
};

struct Effector {
	int add;
	explicit constexpr Effector(const int a): add(a) {}
	static constexpr Effector one() {
		return Effector(0);
	}
	constexpr Effector operator * (const Effector& other) const {
		return Effector(add + other.add);
	}
};

constexpr Monoid operator * (const Monoid& m, const Effector& e) {
	return Monoid(m.min + e.add);
}

struct Segtree {
	struct Node {
		Monoid mn;
		Effector ef;
	};

	int size, log;
	Vec<Node> data;

	void fetch(const int k) {
		assert(1 <= k and k < size);
		data[k].mn = data[2 * k].mn + data[2 * k + 1].mn;
	}
	void apply(const int k, const Effector& e) {
		assert(1 <= k and k < 2 * size);
		data[k].mn = data[k].mn * e;
		data[k].ef = data[k].ef * e;
	}
	void flush(const int k) {
		assert(k < size);
		assert(1 <= k);
		apply(2 * k, data[k].ef);
		apply(2 * k + 1, data[k].ef);
		data[k].ef = Effector::one();
	}

	void push(const int k) {
		const int lsb = __builtin_ctz(k);
		const int width = 31 - __builtin_clz(k);
		for (int d = width; d > lsb; --d) {
			flush(k >> d);
		}
	}
	void pull(int k) {
		k >>= __builtin_ctz(k);
		while (k > 1) {
			k >>= 1;
			fetch(k);
		}
	}

	Segtree(const Vec<int>& vec) {
		log = 0;
		while ((1 << log) < (int) vec.size()) {
			log += 1;
		}
		size = 1 << log;
		data.assign(2 * size, Node{Monoid::zero(), Effector::one()});
		for (int i = 0; i < (int) vec.size(); ++i) {
			data[i + size].mn = Monoid(vec[i]);
		}
		for (int i = size - 1; i > 0; --i) {
			fetch(i);
		}
	}

	void add(int l, int r, const int x) {
		l += size;
		r += size;
		push(l);
		push(r);
		const Effector e(x);
		for (int l0 = l, r0 = r; l0 < r0; l0 >>= 1, r0 >>= 1) {
			if (l0 & 1) apply(l0++, e);
			if (r0 & 1) apply(--r0, e);
		}
		pull(l);
		pull(r);
	}

	void enum_zero(Vec<int>& list) {
		auto dfs = [&](auto&& dfs, const int k) {
			if (data[k].mn.min != 0) {
				return;
			}
			if (k < size) {
				flush(k);
				dfs(dfs, 2 * k);
				dfs(dfs, 2 * k + 1);
			}
			else {
				list.push_back(k - size);
			}
		};
		dfs(dfs, 1);
	}

	void assign(int i, const int v) {
		i += size;
		push(i);
		push(i + 1);
		data[i].mn = Monoid(v);
		pull(i);
		pull(i + 1);
	}
};

int Type;
Vec<int> restore;
Vec<Vec<std::pair<int, int>>> belong;

void init(int k, Vec<int> r) {
	const int n = (int) r.size();
	if (k == 2) {
		Type = 1;
		int b = 0;
		belong.resize(n);
		for (int i = 0; i < n; ++i) {
			if (r[i] == 1 and r[(i + n - 1) % n] == 0) {
				int j = i, k = 0;
				while (true) {
					belong[j].emplace_back(b, k);
					std::cerr << j << ' ';
					j -= 1;
					k += 1;
					if (j < 0) {
						j += n;
					}
					if (r[j] == 1) {
						break;
					}
				}
				std::cerr << std::endl;
				b += 1;
				j = i, k = 0;
				while (true) {
					belong[j].emplace_back(b, k);
					std::cerr << j << ' ';
					if (r[j] == 0) {
						break;
					}
					j += 1;
					k += 1;
					if (j >= n) {
						j -= n;
					}
				}
				b += 1;
				std::cerr << std::endl;
			}
		}
	} else if (2 * k > n) {
		Type = 2;
		restore.resize(n);
		Segtree seg(r);
		std::set<int> zero;
		const auto near_l = [&](const int x) {
			auto itr = zero.lower_bound(x);
			return itr == zero.begin() ? *zero.rbegin() : *std::prev(itr);
		};
		const auto near_r = [&](const int x) {
			auto itr = zero.upper_bound(x);
			return itr == zero.end() ? *zero.begin() : *itr;
		};
		int cand = -1;
		const auto dist = [&](const int l, const int r) {
			return l < r ? r - l : r + n - l;
		};
		for (int max = n - 1; max >= 0; --max) {
			Vec<int> add;
			seg.enum_zero(add);
			for (const auto x: add) {
				seg.assign(x, INF);
				zero.insert(x);
			}
			const auto idx = [&] {
				for (const auto x: add) {
					if (dist(near_l(x), x) >= k) {
						return x;
					}
				}
				return cand;				
			}();
			restore[idx] = max;
			if (idx >= k - 1) {
				seg.add(idx - k + 1, idx, -1);
			}
			else {
				seg.add(0, idx, -1);
				seg.add(n - (k - idx - 1), n, -1);
			}
			zero.erase(idx);	
			cand = zero.empty() ? -1 : near_r(idx);
		}
		for (const auto x: restore) {
			std::cerr << x << ' ';
		}
		std::cerr << std::endl;
	}
}

int compare_plants(int x, int y) {
	if (Type == 1) {
		for (const auto [a, b]: belong[x]) {
			for (const auto [c, d]: belong[y]) {
				if (a == c) {
					return b > d ? 1 : -1;
				}
			}
		}
		return 0;
	} else if (Type == 2) {
		return restore[x] > restore[y] ? 1 : -1;
	}
	return 0;
}

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