oj.uz

Submission #417126

# Submission time Handle Problem Language Result Execution time Memory
417126 2021-06-03T12:00:53 Z KoD Comparing Plants (IOI20_plants) C++17
27 / 100
 977 ms 18300 KB 
#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;

void init(int k, Vec<int> r) {
if (2 * k > (int) r.size()) {
		Type = 2;
		const int n = (int) r.size();
		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) {

	} else if (Type == 2) {
		return restore[x] > restore[y] ? 1 : -1;
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 6 ms 416 KB Output is correct
7 Correct 80 ms 5200 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 84 ms 5340 KB Output is correct
11 Correct 78 ms 5084 KB Output is correct
12 Correct 80 ms 5344 KB Output is correct
13 Correct 80 ms 5188 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 6 ms 416 KB Output is correct
7 Correct 80 ms 5200 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 84 ms 5340 KB Output is correct
11 Correct 78 ms 5084 KB Output is correct
12 Correct 80 ms 5344 KB Output is correct
13 Correct 80 ms 5188 KB Output is correct
14 Correct 150 ms 5676 KB Output is correct
15 Correct 977 ms 14188 KB Output is correct
16 Correct 144 ms 5712 KB Output is correct
17 Correct 951 ms 14016 KB Output is correct
18 Correct 941 ms 18300 KB Output is correct
19 Correct 892 ms 14216 KB Output is correct
20 Correct 968 ms 14148 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -