oj.uz

Submission #837497

# Submission time Handle Problem Language Result Execution time Memory
837497 2023-08-25T11:27:56 Z pavement Comparing Plants (IOI20_plants) C++17
27 / 100
 4000 ms 200696 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());
			auto [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);
			}
		}
		for (int &i : r) {
			i = k - 1 - i;
		}
	}
}

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 1 ms 212 KB Output is correct
3 Correct 0 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 0 ms 212 KB Output is correct
2 Correct 1 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 6 ms 852 KB Output is correct
7 Correct 57 ms 5740 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 872 KB Output is correct
10 Correct 57 ms 5748 KB Output is correct
11 Correct 65 ms 6120 KB Output is correct
12 Correct 60 ms 7520 KB Output is correct
13 Correct 73 ms 5636 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 1 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 6 ms 852 KB Output is correct
7 Correct 57 ms 5740 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 872 KB Output is correct
10 Correct 57 ms 5748 KB Output is correct
11 Correct 65 ms 6120 KB Output is correct
12 Correct 60 ms 7520 KB Output is correct
13 Correct 73 ms 5636 KB Output is correct
14 Correct 146 ms 13468 KB Output is correct
15 Correct 1553 ms 106708 KB Output is correct
16 Correct 139 ms 13444 KB Output is correct
17 Correct 1588 ms 106772 KB Output is correct
18 Correct 1687 ms 149816 KB Output is correct
19 Correct 1661 ms 200696 KB Output is correct
20 Correct 802 ms 106696 KB Output is correct

Subtask #4
0 / 17.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 50 ms 4456 KB Output is correct
4 Correct 2852 ms 169320 KB Output is correct
5 Correct 3417 ms 120428 KB Output is correct
6 Correct 2725 ms 108224 KB Output is correct
7 Correct 2070 ms 106852 KB Output is correct
8 Correct 1694 ms 106788 KB Output is correct
9 Correct 3181 ms 111988 KB Output is correct
10 Execution timed out 4046 ms 126376 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 11.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 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 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 0 ms 212 KB Output is correct
5 Correct 7 ms 836 KB Output is correct
6 Correct 3184 ms 110896 KB Output is correct
7 Correct 2590 ms 109400 KB Output is correct
8 Correct 2189 ms 109340 KB Output is correct
9 Correct 1753 ms 109516 KB Output is correct
10 Correct 3141 ms 114052 KB Output is correct
11 Correct 1931 ms 109428 KB Output is correct
12 Correct 2958 ms 171420 KB Output is correct
13 Correct 3243 ms 122580 KB Output is correct
14 Correct 2692 ms 110672 KB Output is correct
15 Correct 2079 ms 109528 KB Output is correct
16 Execution timed out 4074 ms 144412 KB Time limit exceeded
17 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -