oj.uz

Submission #837535

# Submission time Handle Problem Language Result Execution time Memory
837535 2023-08-25T12:00:45 Z pavement Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 711564 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[200005][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;

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 s = 0; s < n; s++) {
		for (int rep = 0; rep < 2; rep++) {
			::r = r;
			h[s][rep].resize(n);
			root = new node(0, n - 1);
			set<int> zeroes;
			set<ii> candidates;
			
			auto candidates_insert = [&](int a, int b) {
				if (a >= k) {
					candidates.emplace(b, a);
				}
			};
			
			auto candidates_erase = [&](int a, int b) {
				if (a >= k) {
					candidates.erase(mp(b, a));
				}
			};
			
			for (int i = n - 1; i >= 0; i--) {
				while (root->val.first == 0) {
					int cur_pos = root->val.second;
					if (zeroes.empty()) {
						candidates_insert(n, cur_pos);
					} else if ((int)zeroes.size() == 1) {
						int x = *zeroes.begin();
						candidates_erase(n, x);
						candidates_insert(dist(cur_pos, x), x);
						candidates_insert(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(dist(prv, nxt), nxt);
						candidates_insert(dist(prv, cur_pos), cur_pos);
						candidates_insert(dist(cur_pos, nxt), nxt);
					}
					zeroes.insert(cur_pos);
					root->upd(cur_pos, cur_pos, (int)1e9);
				}
				assert(!zeroes.empty());
				auto [pos, len] = *candidates.rbegin();
				if (pos == s) {
					tie(pos, len) = *candidates.begin();
				}
				zeroes.erase(pos);
				{
					candidates_erase(len, pos);
					if ((int)zeroes.size() == 1) {
						candidates_erase(dist(pos, *zeroes.begin()), *zeroes.begin());
						candidates_insert(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(dist(pos, nxt), nxt);
						candidates_insert(dist(prv, nxt), nxt);
					}
				}
				assert(pos != -1);
				h[s][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[x][0][x] < h[x][0][y]) != (h[x][1][x] > h[x][1][y])) {
		return 0;
	} else {
		return (h[x][0][x] < h[x][0][y] ? -1 : 1);
	}
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 6 ms 9640 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 45 ms 13444 KB Output is correct
7 Execution timed out 4088 ms 711564 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 11 ms 11604 KB Output is correct
6 Correct 1149 ms 205264 KB Output is correct
7 Execution timed out 4115 ms 586788 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 4 ms 9684 KB Output is correct
5 Correct 11 ms 11604 KB Output is correct
6 Correct 1149 ms 205264 KB Output is correct
7 Execution timed out 4115 ms 586788 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9636 KB Output is correct
2 Correct 4 ms 9764 KB Output is correct
3 Execution timed out 4072 ms 669624 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9700 KB Output is correct
4 Correct 5 ms 9620 KB Output is correct
5 Correct 5 ms 9812 KB Output is correct
6 Correct 15 ms 11720 KB Output is correct
7 Correct 132 ms 28176 KB Output is correct
8 Correct 120 ms 28220 KB Output is correct
9 Correct 119 ms 28188 KB Output is correct
10 Correct 119 ms 28228 KB Output is correct
11 Correct 127 ms 28124 KB Output is correct
12 Correct 130 ms 28120 KB Output is correct
13 Correct 95 ms 28200 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9684 KB Output is correct
2 Correct 6 ms 9652 KB Output is correct
3 Correct 6 ms 9660 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 1400 ms 205700 KB Output is correct
6 Execution timed out 4035 ms 425448 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9684 KB Output is correct
2 Correct 4 ms 9684 KB Output is correct
3 Correct 4 ms 9684 KB Output is correct
4 Correct 6 ms 9640 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 45 ms 13444 KB Output is correct
7 Execution timed out 4088 ms 711564 KB Time limit exceeded
8 Halted 0 ms 0 KB -