oj.uz

Submission #770910

# Submission time Handle Problem Language Result Execution time Memory
770910 2023-07-02T06:19:52 Z SanguineChameleon Comparing Plants (IOI20_plants) C++17
5 / 100
 65 ms 6524 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 20;
const int inf = 1e9 + 20;
int a[maxn];
int tree[maxn * 4];
int lazy[maxn * 4];
int pos[maxn];
int dp_left[maxn];
int dp_right[maxn];
int n, k;
set<int> all_zeroes, good_zeroes;

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tree[id] = a[lt];
		return;
	}
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt);
	build(id * 2 + 1, mt + 1, rt);
	tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
}

void update(int id, int lt, int rt, int ql, int qr, int add) {
	if (lt == ql && rt == qr) {
		tree[id] += add;
		lazy[id] += add;
		return;
	}
	tree[id * 2] += lazy[id];
	lazy[id * 2] += lazy[id];
	tree[id * 2 + 1] += lazy[id];
	lazy[id * 2 + 1] += lazy[id];
	lazy[id] = 0;
	int mt = (lt + rt) / 2;
	if (qr <= mt) {
		update(id * 2, lt, mt, ql, qr, add);
	}
	else if (ql >= mt + 1) {
		update(id * 2 + 1, mt + 1, rt, ql, qr, add);
	}
	else {
		update(id * 2, lt, mt, ql, mt, add);
		update(id * 2 + 1, mt + 1, rt, mt + 1, qr, add);
	}
	tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
}

bool contains(int x, int y) {
	if (x < y) {
		return y - x + 1 <= k;
	}
	else {
		return n - (x - y - 1) <= k;
	}
}

void add_zero(int x) {
	auto it = all_zeroes.insert(x).first;
	int prv = (it == all_zeroes.begin() ? *all_zeroes.rbegin() : *prev(it));
	if (!contains(prv, x)) {
		good_zeroes.insert(x);
	} 
	int nxt = (next(it) == all_zeroes.end() ? *all_zeroes.begin() : *next(it));
	if (contains(x, nxt)) {
		assert(false);
		good_zeroes.erase(nxt);
	}
	else {
		good_zeroes.insert(nxt);
	}
}

void rem_zero(int x) {
	auto it = all_zeroes.find(x);
	int prv = (it == all_zeroes.begin() ? *all_zeroes.rbegin() : *prev(it));
	int nxt = (next(it) == all_zeroes.end() ? *all_zeroes.begin() : *next(it));
	if (contains(prv, nxt)) {
		good_zeroes.erase(nxt);
	}
	else {
		good_zeroes.insert(nxt);
	}
	int rt = x;
	int lt = (rt + n - (k - 1)) % n;
	if (lt <= rt) {
		update(1, 0, n - 1, lt, rt, -1);
	}
	else {
		update(1, 0, n - 1, lt, n - 1, -1);
		update(1, 0, n - 1, 0, rt, -1);
	}
	all_zeroes.erase(it);
	good_zeroes.erase(x);
}

void find_zeroes(int id, int lt, int rt) {
	if (tree[id] > 0) {
		return;
	}
	if (lt == rt) {
		add_zero(lt);
		tree[id] = inf;
		lazy[id] = 0;
		return;
	}
	tree[id * 2] += lazy[id];
	lazy[id * 2] += lazy[id];
	tree[id * 2 + 1] += lazy[id];
	lazy[id * 2 + 1] += lazy[id];
	lazy[id] = 0;
	int mt = (lt + rt) / 2;
	find_zeroes(id * 2, lt, mt);
	find_zeroes(id * 2 + 1, mt + 1, rt);
	tree[id] = min(tree[id * 2], tree[id * 2 + 1]);
}

void init(int _k, vector<int> _a) {
	n = _a.size();
	k = _k;
	for (int i = 0; i < n; i++) {
		a[i] = k - 1 - _a[i];
	}
	if (k == 2) {
		for (int i = 0; i < n; i++) {
			if (a[i] == 0) {
				dp_right[i] = i;
				for (int j = (i + n - 1) % n; j != i; j = (j + n - 1) % n) {
					dp_right[j] = (a[j] ? dp_right[(j + 1) % n] : j);
				}
				break;
			}
		}
		for (int i = 0; i < n; i++) {
			if (a[(i + n - 1) % n] == 1) {
				dp_left[i] = i;
				for (int j = (i + 1) % n; j != i; j = (j + 1) % n) {
					dp_left[j] = (!a[(j + n - 1) % n] ? dp_left[(j + n - 1) % n] : j);
				}
				break;
			}
		}
	}
	else {
		build(1, 0, n - 1);
		for (int i = 0; i < n; i++) {
			find_zeroes(1, 0, n - 1);
			pos[*good_zeroes.begin()] = i;
			rem_zero(*good_zeroes.begin());
		}
	}
	return;
}

bool check(int x, int y) {
	if (dp_left[x] == dp_right[x]) {
		return (dp_left[x] != x);
	}
	else if (dp_left[x] < dp_right[x]) {
		return dp_left[x] <= y && y <= dp_right[x];
	}
	else {
		return (y >= dp_left[x] || y <= dp_right[x]);
	}
}

int compare_plants(int x, int y) {
	if (k == 2) {
		if (check(x, y)) {
			return 1;
		}
		else if (check(y, x)) {
			return -1;
		}
		else {
			return 0;
		}
	}
	else {
		return (pos[x] > pos[y] ? 1 : -1);
	}
}

Subtask #1
5.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 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 41 ms 3116 KB Output is correct
7 Correct 45 ms 3420 KB Output is correct
8 Correct 63 ms 6476 KB Output is correct
9 Correct 60 ms 6508 KB Output is correct
10 Correct 65 ms 6516 KB Output is correct
11 Correct 63 ms 6524 KB Output is correct
12 Correct 61 ms 6516 KB Output is correct
13 Correct 59 ms 6524 KB Output is correct
14 Correct 58 ms 6484 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 1 ms 212 KB Output is correct
4 Runtime error 1 ms 468 KB Execution killed with signal 6
5 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 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 41 ms 3116 KB Output is correct
7 Correct 45 ms 3420 KB Output is correct
8 Correct 63 ms 6476 KB Output is correct
9 Correct 60 ms 6508 KB Output is correct
10 Correct 65 ms 6516 KB Output is correct
11 Correct 63 ms 6524 KB Output is correct
12 Correct 61 ms 6516 KB Output is correct
13 Correct 59 ms 6524 KB Output is correct
14 Correct 58 ms 6484 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Runtime error 1 ms 468 KB Execution killed with signal 6
19 Halted 0 ms 0 KB -