oj.uz

Submission #607221

# Submission time Handle Problem Language Result Execution time Memory
607221 2022-07-26T13:29:37 Z Temmie Comparing Plants (IOI20_plants) C++17
100 / 100
 1071 ms 55800 KB 
#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, size);
	}
	
	void build(const std::vector <int>& a, int now, int l, int r) {
		if (!(r - l - 1)) {
			if (l < (int) a.size()) {
				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);
		push(now * 2 + 1, l, mid);
		push(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;

inline bool between(int from, int to, int subj) {
	if (from <= to) {
		return from <= subj && subj <= to;
	}
	return from == subj || to == subj || !between(to, from, subj);
}

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 || between(bin_left[b - 1][i], i, bin_left[b - 1][bin_left[b - 1][i]])
			? -1 : bin_left[b - 1][bin_left[b - 1][i]];
			bin_right[b][i] = bin_right[b - 1][i] == -1 || between(i, bin_right[b - 1][i], bin_right[b - 1][bin_right[b - 1][i]])
			? -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) {
				d -= dist(bin_left[b][ind], ind);
				ind = bin_left[b][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) {
				d -= dist(ind, bin_right[b][ind]);
				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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 64 ms 3044 KB Output is correct
7 Correct 151 ms 7340 KB Output is correct
8 Correct 638 ms 50544 KB Output is correct
9 Correct 650 ms 50508 KB Output is correct
10 Correct 680 ms 50508 KB Output is correct
11 Correct 735 ms 50644 KB Output is correct
12 Correct 729 ms 50612 KB Output is correct
13 Correct 675 ms 50564 KB Output is correct
14 Correct 747 ms 50508 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 94 ms 4220 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 87 ms 6244 KB Output is correct
11 Correct 93 ms 6116 KB Output is correct
12 Correct 122 ms 6232 KB Output is correct
13 Correct 92 ms 6252 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 94 ms 4220 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 6 ms 596 KB Output is correct
10 Correct 87 ms 6244 KB Output is correct
11 Correct 93 ms 6116 KB Output is correct
12 Correct 122 ms 6232 KB Output is correct
13 Correct 92 ms 6252 KB Output is correct
14 Correct 146 ms 9500 KB Output is correct
15 Correct 1014 ms 51444 KB Output is correct
16 Correct 152 ms 9556 KB Output is correct
17 Correct 924 ms 51344 KB Output is correct
18 Correct 937 ms 51060 KB Output is correct
19 Correct 1022 ms 51464 KB Output is correct
20 Correct 1000 ms 51508 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 89 ms 3544 KB Output is correct
4 Correct 847 ms 55100 KB Output is correct
5 Correct 905 ms 51756 KB Output is correct
6 Correct 952 ms 51020 KB Output is correct
7 Correct 939 ms 51100 KB Output is correct
8 Correct 997 ms 51268 KB Output is correct
9 Correct 758 ms 51636 KB Output is correct
10 Correct 842 ms 50628 KB Output is correct
11 Correct 721 ms 50516 KB Output is correct
12 Correct 838 ms 50712 KB Output is correct
13 Correct 885 ms 50732 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 416 KB Output is correct
7 Correct 18 ms 1236 KB Output is correct
8 Correct 17 ms 1236 KB Output is correct
9 Correct 19 ms 1272 KB Output is correct
10 Correct 21 ms 1224 KB Output is correct
11 Correct 24 ms 1228 KB Output is correct
12 Correct 20 ms 1208 KB Output is correct
13 Correct 23 ms 1236 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 744 ms 49872 KB Output is correct
7 Correct 746 ms 50008 KB Output is correct
8 Correct 728 ms 50212 KB Output is correct
9 Correct 963 ms 50356 KB Output is correct
10 Correct 710 ms 50876 KB Output is correct
11 Correct 779 ms 50364 KB Output is correct
12 Correct 738 ms 55380 KB Output is correct
13 Correct 731 ms 51180 KB Output is correct
14 Correct 819 ms 50156 KB Output is correct
15 Correct 849 ms 50244 KB Output is correct
16 Correct 627 ms 49684 KB Output is correct
17 Correct 685 ms 49860 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 64 ms 3044 KB Output is correct
7 Correct 151 ms 7340 KB Output is correct
8 Correct 638 ms 50544 KB Output is correct
9 Correct 650 ms 50508 KB Output is correct
10 Correct 680 ms 50508 KB Output is correct
11 Correct 735 ms 50644 KB Output is correct
12 Correct 729 ms 50612 KB Output is correct
13 Correct 675 ms 50564 KB Output is correct
14 Correct 747 ms 50508 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 4 ms 468 KB Output is correct
21 Correct 94 ms 4220 KB Output is correct
22 Correct 3 ms 340 KB Output is correct
23 Correct 6 ms 596 KB Output is correct
24 Correct 87 ms 6244 KB Output is correct
25 Correct 93 ms 6116 KB Output is correct
26 Correct 122 ms 6232 KB Output is correct
27 Correct 92 ms 6252 KB Output is correct
28 Correct 146 ms 9500 KB Output is correct
29 Correct 1014 ms 51444 KB Output is correct
30 Correct 152 ms 9556 KB Output is correct
31 Correct 924 ms 51344 KB Output is correct
32 Correct 937 ms 51060 KB Output is correct
33 Correct 1022 ms 51464 KB Output is correct
34 Correct 1000 ms 51508 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 89 ms 3544 KB Output is correct
38 Correct 847 ms 55100 KB Output is correct
39 Correct 905 ms 51756 KB Output is correct
40 Correct 952 ms 51020 KB Output is correct
41 Correct 939 ms 51100 KB Output is correct
42 Correct 997 ms 51268 KB Output is correct
43 Correct 758 ms 51636 KB Output is correct
44 Correct 842 ms 50628 KB Output is correct
45 Correct 721 ms 50516 KB Output is correct
46 Correct 838 ms 50712 KB Output is correct
47 Correct 885 ms 50732 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 2 ms 416 KB Output is correct
54 Correct 18 ms 1236 KB Output is correct
55 Correct 17 ms 1236 KB Output is correct
56 Correct 19 ms 1272 KB Output is correct
57 Correct 21 ms 1224 KB Output is correct
58 Correct 24 ms 1228 KB Output is correct
59 Correct 20 ms 1208 KB Output is correct
60 Correct 23 ms 1236 KB Output is correct
61 Correct 88 ms 5216 KB Output is correct
62 Correct 151 ms 9420 KB Output is correct
63 Correct 745 ms 50488 KB Output is correct
64 Correct 886 ms 50700 KB Output is correct
65 Correct 985 ms 50900 KB Output is correct
66 Correct 914 ms 51224 KB Output is correct
67 Correct 943 ms 51324 KB Output is correct
68 Correct 830 ms 52424 KB Output is correct
69 Correct 932 ms 51312 KB Output is correct
70 Correct 894 ms 55800 KB Output is correct
71 Correct 1071 ms 51812 KB Output is correct
72 Correct 980 ms 51080 KB Output is correct
73 Correct 907 ms 51088 KB Output is correct
74 Correct 727 ms 50664 KB Output is correct
75 Correct 830 ms 50744 KB Output is correct