oj.uz

Submission #837432

# Submission time Handle Problem Language Result Execution time Memory
837432 2023-08-25T10:48:07 Z pavement Comparing Plants (IOI20_plants) C++17
44 / 100
 3976 ms 304068 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;
		set<ii> candidates;
		for (int i = n - 1; i >= 0; i--) {
			while (root->val.first == 0) {
				int cur_pos = root->val.second;
				if (zeroes.empty()) {
					candidates.emplace(n, cur_pos);
					root2->upd(n, cur_pos);
				} else if ((int)zeroes.size() == 1) {
					int x = *zeroes.begin();
					candidates.erase(mp(n, x));
					root2->del(n, x);
					candidates.emplace(dist(cur_pos, x), x);
					root2->upd(dist(cur_pos, x), x);
					candidates.emplace(dist(x, cur_pos), cur_pos);
					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;
					candidates.erase(mp(dist(prv, nxt), nxt));
					root2->del(dist(prv, nxt), nxt);
					candidates.emplace(mp(dist(prv, cur_pos), cur_pos));
					root2->upd(dist(prv, cur_pos), cur_pos);
					candidates.emplace(mp(dist(cur_pos, nxt), nxt));
					root2->upd(dist(cur_pos, nxt), nxt);
				}
				zeroes.insert(cur_pos);
				root->upd(cur_pos, cur_pos, (int)1e9);
			}
			assert(!zeroes.empty() && !candidates.empty());
			auto [pos, len] = (rep == 0 ? root2->qry(k, n).first : root2->qry(k, n).second);
			zeroes.erase(pos);
			{
				root2->del(len, pos);
				candidates.erase(mp(len, pos));
				if ((int)zeroes.size() == 1) {
					candidates.erase(mp(dist(pos, *zeroes.begin()), *zeroes.begin()));
					root2->del(dist(pos, *zeroes.begin()), *zeroes.begin());
					candidates.emplace(n, *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;
					candidates.erase(mp(dist(pos, nxt), nxt));
					root2->del(dist(pos, nxt), nxt);
					candidates.emplace(dist(prv, 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 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 288 KB Output is correct
4 Incorrect 1 ms 272 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 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 1 ms 340 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 61 ms 7532 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 5 ms 828 KB Output is correct
10 Correct 60 ms 7636 KB Output is correct
11 Correct 84 ms 9384 KB Output is correct
12 Correct 48 ms 7684 KB Output is correct
13 Correct 53 ms 7532 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 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 852 KB Output is correct
7 Correct 61 ms 7532 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 5 ms 828 KB Output is correct
10 Correct 60 ms 7636 KB Output is correct
11 Correct 84 ms 9384 KB Output is correct
12 Correct 48 ms 7684 KB Output is correct
13 Correct 53 ms 7532 KB Output is correct
14 Correct 138 ms 15752 KB Output is correct
15 Correct 1570 ms 110484 KB Output is correct
16 Correct 157 ms 15668 KB Output is correct
17 Correct 1673 ms 110404 KB Output is correct
18 Correct 2957 ms 208688 KB Output is correct
19 Correct 582 ms 110468 KB Output is correct
20 Correct 840 ms 110540 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 57 ms 6312 KB Output is correct
4 Correct 2582 ms 175432 KB Output is correct
5 Correct 3087 ms 121144 KB Output is correct
6 Correct 2769 ms 108268 KB Output is correct
7 Correct 2343 ms 106928 KB Output is correct
8 Correct 1814 ms 106784 KB Output is correct
9 Correct 3831 ms 155420 KB Output is correct
10 Correct 3976 ms 127600 KB Output is correct
11 Correct 3179 ms 304068 KB Output is correct
12 Correct 522 ms 106828 KB Output is correct
13 Correct 3178 ms 245016 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 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 232 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 #7
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 288 KB Output is correct
4 Incorrect 1 ms 272 KB Output isn't correct
5 Halted 0 ms 0 KB -