oj.uz

Submission #837500

# Submission time Handle Problem Language Result Execution time Memory
837500 2023-08-25T11:31:04 Z pavement Comparing Plants (IOI20_plants) C++17
27 / 100
 4000 ms 200700 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;
	set<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(mp(v, p));
		if (S == E) {
			return;
		}
		int M = (S + E) / 2;
		if (p <= M) {
			left->del(p, v);
		} else {
			right->del(p, v);
		}
	}
	ii qry(int l, int r) {
		if (l > E || r < S) {
			return mp(-(int)1e9, -1);
		}
		if (l <= S && E <= r) {
			if (val.empty()) {
				return mp(-(int)1e9, -1);
			} else {
				return *val.rbegin();
			}
		}
		return max(left->qry(l, r), right->qry(l, r));
	}
} *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(1, 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);
			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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 276 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 4 ms 852 KB Output is correct
7 Correct 57 ms 5640 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 61 ms 5744 KB Output is correct
11 Correct 63 ms 6040 KB Output is correct
12 Correct 62 ms 7500 KB Output is correct
13 Correct 57 ms 5620 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 4 ms 852 KB Output is correct
7 Correct 57 ms 5640 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 4 ms 852 KB Output is correct
10 Correct 61 ms 5744 KB Output is correct
11 Correct 63 ms 6040 KB Output is correct
12 Correct 62 ms 7500 KB Output is correct
13 Correct 57 ms 5620 KB Output is correct
14 Correct 145 ms 13440 KB Output is correct
15 Correct 1431 ms 106772 KB Output is correct
16 Correct 145 ms 13444 KB Output is correct
17 Correct 1452 ms 106772 KB Output is correct
18 Correct 1649 ms 149812 KB Output is correct
19 Correct 1687 ms 200700 KB Output is correct
20 Correct 856 ms 106692 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 0 ms 212 KB Output is correct
3 Correct 55 ms 4436 KB Output is correct
4 Correct 3097 ms 169380 KB Output is correct
5 Correct 3670 ms 120524 KB Output is correct
6 Correct 2731 ms 108240 KB Output is correct
7 Correct 2083 ms 106860 KB Output is correct
8 Correct 1651 ms 106712 KB Output is correct
9 Correct 3430 ms 111948 KB Output is correct
10 Execution timed out 4094 ms 126316 KB Time limit exceeded
11 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 0 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 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 6 ms 828 KB Output is correct
6 Correct 3464 ms 108572 KB Output is correct
7 Correct 2697 ms 106984 KB Output is correct
8 Correct 2252 ms 106728 KB Output is correct
9 Correct 1731 ms 106892 KB Output is correct
10 Correct 3436 ms 111900 KB Output is correct
11 Correct 2106 ms 106700 KB Output is correct
12 Correct 2993 ms 169404 KB Output is correct
13 Correct 3397 ms 120404 KB Output is correct
14 Correct 2797 ms 108256 KB Output is correct
15 Correct 2050 ms 106916 KB Output is correct
16 Execution timed out 4088 ms 142356 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 276 KB Output isn't correct
5 Halted 0 ms 0 KB -