oj.uz

Submission #837437

# Submission time Handle Problem Language Result Execution time Memory
837437 2023-08-25T10:51:53 Z pavement Comparing Plants (IOI20_plants) C++17
27 / 100
 4000 ms 203468 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;
			if (rep == 0) {
				auto tmp = root2->qry(k, n).first;
				if (tmp.first != 0) {
					tmp = root2->qry(k, n).second;
				}
				tie(pos, len) = tmp;
			} else {
				tie(pos, len) = root2->qry(k, n).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 1 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 1 ms 296 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 340 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 55 ms 7528 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 59 ms 7756 KB Output is correct
11 Correct 69 ms 9256 KB Output is correct
12 Correct 48 ms 7648 KB Output is correct
13 Correct 53 ms 7628 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 1 ms 296 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 340 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 55 ms 7528 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 59 ms 7756 KB Output is correct
11 Correct 69 ms 9256 KB Output is correct
12 Correct 48 ms 7648 KB Output is correct
13 Correct 53 ms 7628 KB Output is correct
14 Correct 140 ms 15692 KB Output is correct
15 Correct 1520 ms 109512 KB Output is correct
16 Correct 145 ms 15676 KB Output is correct
17 Correct 1500 ms 109592 KB Output is correct
18 Correct 2715 ms 203468 KB Output is correct
19 Correct 504 ms 109560 KB Output is correct
20 Correct 866 ms 109576 KB Output is correct

Subtask #4
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 51 ms 6228 KB Output is correct
4 Correct 2919 ms 172132 KB Output is correct
5 Correct 3483 ms 122052 KB Output is correct
6 Correct 2718 ms 109736 KB Output is correct
7 Correct 2109 ms 108384 KB Output is correct
8 Correct 1710 ms 108312 KB Output is correct
9 Execution timed out 4011 ms 154624 KB Time limit exceeded
10 Halted 0 ms 0 KB -

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 1 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 260 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 Incorrect 6 ms 852 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 1 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 -