oj.uz

Submission #837506

# Submission time Handle Problem Language Result Execution time Memory
837506 2023-08-25T11:36:53 Z pavement Comparing Plants (IOI20_plants) C++17
59 / 100
 652 ms 53500 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;

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);
		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();
			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[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 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 48 ms 4084 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 49 ms 4172 KB Output is correct
11 Correct 45 ms 4000 KB Output is correct
12 Correct 46 ms 4300 KB Output is correct
13 Correct 46 ms 4064 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 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 48 ms 4084 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 49 ms 4172 KB Output is correct
11 Correct 45 ms 4000 KB Output is correct
12 Correct 46 ms 4300 KB Output is correct
13 Correct 46 ms 4064 KB Output is correct
14 Correct 81 ms 7244 KB Output is correct
15 Correct 625 ms 44140 KB Output is correct
16 Correct 78 ms 7244 KB Output is correct
17 Correct 625 ms 44116 KB Output is correct
18 Correct 337 ms 44160 KB Output is correct
19 Correct 328 ms 48840 KB Output is correct
20 Correct 529 ms 44028 KB Output is correct

Subtask #4
17.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 43 ms 3532 KB Output is correct
4 Correct 406 ms 47268 KB Output is correct
5 Correct 468 ms 44748 KB Output is correct
6 Correct 580 ms 44236 KB Output is correct
7 Correct 649 ms 44184 KB Output is correct
8 Correct 652 ms 44028 KB Output is correct
9 Correct 408 ms 44560 KB Output is correct
10 Correct 402 ms 45132 KB Output is correct
11 Correct 270 ms 44140 KB Output is correct
12 Correct 293 ms 53500 KB Output is correct
13 Correct 331 ms 44068 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 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
15.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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 450 ms 44288 KB Output is correct
7 Correct 587 ms 44044 KB Output is correct
8 Correct 643 ms 44104 KB Output is correct
9 Correct 635 ms 44140 KB Output is correct
10 Correct 388 ms 44564 KB Output is correct
11 Correct 434 ms 44140 KB Output is correct
12 Correct 366 ms 47180 KB Output is correct
13 Correct 440 ms 44748 KB Output is correct
14 Correct 544 ms 44104 KB Output is correct
15 Correct 631 ms 44112 KB Output is correct
16 Correct 398 ms 45936 KB Output is correct
17 Correct 422 ms 46732 KB Output is correct

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 -