oj.uz

Submission #837444

# Submission time Handle Problem Language Result Execution time Memory
837444 2023-08-25T10:56:59 Z pavement Comparing Plants (IOI20_plants) C++17
44 / 100
 3675 ms 296084 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair

using ii = pair<int, int>;

int n;
vector<int> r, h[2];

struct node {
	node *left, *right;
	int S, E, pv;
	ii val;
	node(int _s, int _e) : S(_s), E(_e), pv(0) {
		if (S == E) {
			val = mp(r[S], S);
			return;
		}
		int M = (S + E) / 2;
		left = new node(S, M);
		right = new node(M + 1, E);
		val = min(left->val, right->val);
	}
	void prop() {
		if (S == E || !pv) {
			return;
		}
		left->val.first += pv;
		left->pv += pv;
		right->val.first += pv;
		right->pv += pv;
		pv = 0;
	}
	void upd(int l, int r, int v) {
		if (l > E || r < S) {
			return;
		}
		if (l <= S && E <= r) {
			val.first += v;
			pv += v;
			return;
		}
		prop();
		left->upd(l, r, v);
		right->upd(l, r, v);
		val = min(left->val, right->val);
	}
} *root;

struct node2 {
	node2 *left, *right;
	int S, E;
	multiset<ii> val;
	node2(int _s, int _e) : S(_s), E(_e) {
		if (S == E) {
			return;
		}
		int M = (S + E) / 2;
		left = new node2(S, M);
		right = new node2(M + 1, E);
	}
	void upd(int p, int v) {
		val.emplace(v, p);
		if (S == E) {
			return;
		}
		int M = (S + E) / 2;
		if (p <= M) {
			left->upd(p, v);
		} else {
			right->upd(p, v);
		}
	}
	void del(int p, int v) {
		val.erase(val.find(mp(v, p)));
		if (S == E) {
			return;
		}
		int M = (S + E) / 2;
		if (p <= M) {
			left->del(p, v);
		} else {
			right->del(p, v);
		}
	}
	pair<ii, ii> qry(int l, int r) {
		if (l > E || r < S) {
			return mp(mp((int)1e9, -1), mp(-(int)1e9, -1));
		}
		if (l <= S && E <= r) {
			if (val.empty()) {
				return mp(mp((int)1e9, -1), mp(-(int)1e9, -1));
			} else {
				return mp(*val.begin(), *val.rbegin());
			}
		}
		auto lq = left->qry(l, r), rq = right->qry(l, r);
		return mp(min(lq.first, rq.first), max(lq.second, rq.second));
	}
} *root2;

void init(int k, vector<int> r) {
	n = (int)r.size();
	
	auto dist = [&](int i, int j) {
		int ret = j - i;
		if (ret < 0) {
			return ret + n;
		} else {
			return ret;
		}
	};
	
	for (int rep = 0; rep < 2; rep++) {
		::r = r;
		h[rep].resize(n);
		root = new node(0, n - 1);
		root2 = new node2(0, n);
		set<int> zeroes;
		for (int i = n - 1; i >= 0; i--) {
			while (root->val.first == 0) {
				int cur_pos = root->val.second;
				if (zeroes.empty()) {
					root2->upd(n, cur_pos);
				} else if ((int)zeroes.size() == 1) {
					int x = *zeroes.begin();
					root2->del(n, x);
					root2->upd(dist(cur_pos, x), x);
					root2->upd(dist(x, cur_pos), cur_pos);
				} else {
					auto it = zeroes.lower_bound(cur_pos);
					if (it == zeroes.end()) {
						it = zeroes.begin();
					}
					int nxt = *it;
					if (it == zeroes.begin()) {
						it = zeroes.end();
					}
					--it;
					int prv = *it;
					root2->del(dist(prv, nxt), nxt);
					root2->upd(dist(prv, cur_pos), cur_pos);
					root2->upd(dist(cur_pos, nxt), nxt);
				}
				zeroes.insert(cur_pos);
				root->upd(cur_pos, cur_pos, (int)1e9);
			}
			assert(!zeroes.empty());
			int pos = -1, len = -1;
			auto res = root2->qry(k, n);
			if (rep == 0) {
				auto tmp = res.first;
				bool zero_active = (!root2->val.empty() && root2->val.lower_bound(mp(0, 0))->first == 0);
				if (tmp.first != 0 && zero_active) {
					tmp = res.second;
				}
				tie(pos, len) = tmp;
			} else {
				tie(pos, len) = res.second;
			}
			zeroes.erase(pos);
			{
				root2->del(len, pos);
				if ((int)zeroes.size() == 1) {
					root2->del(dist(pos, *zeroes.begin()), *zeroes.begin());
					root2->upd(n, *zeroes.begin());
				} else if ((int)zeroes.size() >= 2) {
					auto it = zeroes.lower_bound(pos);
					if (it == zeroes.end()) {
						it = zeroes.begin();
					}
					int nxt = *it;
					if (it == zeroes.begin()) {
						it = zeroes.end();
					}
					--it;
					int prv = *it;
					root2->del(dist(pos, nxt), nxt);
					root2->upd(dist(prv, nxt), nxt);
				}
			}
			assert(pos != -1);
			h[rep][pos] = i;
			if (pos - k + 1 < 0) {
				root->upd(pos - k + 1 + n, n - 1, -1);
				root->upd(0, pos - 1, -1);
			} else {
				root->upd(pos - k + 1, pos - 1, -1);
			}
		}
	}
}

int compare_plants(int x, int y) {
	if ((h[0][x] < h[0][y]) != (h[1][x] < h[1][y])) {
		return 0;
	} else {
		return (h[0][x] < h[0][y] ? -1 : 1);
	}
}

Subtask #1
0 / 5.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 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.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 340 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 59 ms 5620 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 7 ms 900 KB Output is correct
10 Correct 58 ms 5736 KB Output is correct
11 Correct 72 ms 7392 KB Output is correct
12 Correct 48 ms 5836 KB Output is correct
13 Correct 55 ms 5724 KB Output is correct

Subtask #3
13.0 / 13.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 340 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 59 ms 5620 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 7 ms 900 KB Output is correct
10 Correct 58 ms 5736 KB Output is correct
11 Correct 72 ms 7392 KB Output is correct
12 Correct 48 ms 5836 KB Output is correct
13 Correct 55 ms 5724 KB Output is correct
14 Correct 171 ms 13476 KB Output is correct
15 Correct 1538 ms 106704 KB Output is correct
16 Correct 165 ms 13480 KB Output is correct
17 Correct 1633 ms 106708 KB Output is correct
18 Correct 2967 ms 200692 KB Output is correct
19 Correct 523 ms 106760 KB Output is correct
20 Correct 994 ms 106768 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 1 ms 212 KB Output is correct
3 Correct 54 ms 4516 KB Output is correct
4 Correct 2745 ms 169320 KB Output is correct
5 Correct 2931 ms 120448 KB Output is correct
6 Correct 2622 ms 108260 KB Output is correct
7 Correct 2072 ms 106856 KB Output is correct
8 Correct 1725 ms 106776 KB Output is correct
9 Correct 3298 ms 153088 KB Output is correct
10 Correct 3675 ms 127928 KB Output is correct
11 Correct 2843 ms 296084 KB Output is correct
12 Correct 518 ms 108276 KB Output is correct
13 Correct 2940 ms 239836 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 232 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Incorrect 6 ms 724 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 1 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -