oj.uz

Submission #837359

# Submission time Handle Problem Language Result Execution time Memory
837359 2023-08-25T09:53:35 Z pavement Comparing Plants (IOI20_plants) C++17
44 / 100
 366 ms 46264 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;

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();
	::r = r;
	h.resize(n);
	root = new node(0, n - 1);
	set<int> zeroes;
	set<ii> candidates;
	
	auto dist = [&](int i, int j) {
		int ret = j - i;
		if (ret < 0) {
			return ret + n;
		} else {
			return ret;
		}
	};
	
	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);
			} else if ((int)zeroes.size() == 1) {
				int x = *zeroes.begin();
				candidates.erase(mp(n, x));
				candidates.emplace(dist(cur_pos, x), x);
				candidates.emplace(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));
				candidates.emplace(mp(dist(prv, cur_pos), cur_pos));
				candidates.emplace(mp(dist(cur_pos, nxt), nxt));
			}
			zeroes.insert(cur_pos);
			root->upd(cur_pos, cur_pos, (int)1e9);
		}
		assert(!zeroes.empty() && !candidates.empty());
		int pos = candidates.rbegin()->second;
		zeroes.erase(pos);
		{
			candidates.erase(--candidates.end());
			if ((int)zeroes.size() == 1) {
				candidates.clear();
				candidates.emplace(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));
				candidates.emplace(dist(prv, nxt), nxt);
			}
		}
		assert(pos != -1);
		h[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) {
	return (h[x] < h[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 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 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 1 ms 212 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 46 ms 3700 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 45 ms 3668 KB Output is correct
11 Correct 41 ms 3804 KB Output is correct
12 Correct 39 ms 3704 KB Output is correct
13 Correct 42 ms 3588 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 46 ms 3700 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 45 ms 3668 KB Output is correct
11 Correct 41 ms 3804 KB Output is correct
12 Correct 39 ms 3704 KB Output is correct
13 Correct 42 ms 3588 KB Output is correct
14 Correct 59 ms 5416 KB Output is correct
15 Correct 351 ms 24528 KB Output is correct
16 Correct 72 ms 5296 KB Output is correct
17 Correct 339 ms 24652 KB Output is correct
18 Correct 324 ms 33960 KB Output is correct
19 Correct 167 ms 24476 KB Output is correct
20 Correct 288 ms 24648 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 0 ms 212 KB Output is correct
3 Correct 39 ms 3308 KB Output is correct
4 Correct 247 ms 30832 KB Output is correct
5 Correct 301 ms 29000 KB Output is correct
6 Correct 357 ms 27880 KB Output is correct
7 Correct 366 ms 27988 KB Output is correct
8 Correct 354 ms 28240 KB Output is correct
9 Correct 278 ms 32240 KB Output is correct
10 Correct 307 ms 29156 KB Output is correct
11 Correct 317 ms 46264 KB Output is correct
12 Correct 138 ms 27608 KB Output is correct
13 Correct 360 ms 40980 KB Output is correct

Subtask #5
0 / 11.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 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 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 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -