oj.uz

Submission #770968

# Submission time Handle Problem Language Result Execution time Memory
770968 2023-07-02T08:32:53 Z SanguineChameleon Comparing Plants (IOI20_plants) C++17
30 / 100
 510 ms 96276 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 20;
const int maxk = 20;
const int inf = 1e9 + 20;
int a[maxn];
int tree[maxn * 4];
int lazy[maxn * 4];
int step_left[maxn][maxk];
int step_right[maxn][maxk];
int height[maxn];
set<int> all_zeroes, good_zeroes;
int n, k;

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)) {
		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]);
}

int dist_right(int x, int y) {
	return (y + n - x) % n;
}

int dist_left(int x, int y) {
	return (x + n - y) % n;
}

void init(int _k, vector<int> _a) {
	n = _a.size();
	k = _k;
	for (int i = 0; i < n; i++) {
		a[i] = _a[i];
	}
	build(1, 0, n - 1);
	for (int i = n - 1; i >= 0; i--) {
		find_zeroes(1, 0, n - 1);
		height[*good_zeroes.begin()] = i;
		rem_zero(*good_zeroes.begin());
	}
	set<pair<int, int>> heights;
	for (int i = 0; i < k - 1; i++) {
		heights.emplace(height[i], i);
	}
	for (int i = 0; i < n; i++) {
		int prv = (i + n - 1) % n;
		int nxt = (i + k - 1) % n;
		auto it = heights.upper_bound(make_pair(height[prv], prv));
		step_right[prv][0] = (it == heights.end() ? 0 : dist_right(prv, it->second));
		it = heights.upper_bound(make_pair(height[nxt], nxt));
		step_left[nxt][0] = (it == heights.end() ? 0 : dist_left(nxt, it->second));
		heights.erase(make_pair(height[i], i));
		heights.emplace(height[nxt], nxt);
	}
	for (int k = 1; k < maxk; k++) {
		for (int i = 0; i < n; i++) {
			step_right[i][k] = step_right[i][k - 1] + step_right[(i + step_right[i][k - 1]) % n][k - 1];
			step_left[i][k] = step_left[i][k - 1] + step_left[(i + n - step_left[i][k - 1] % n) % n][k - 1];
		}
	}
	return;
}

int check_left(int x, int y) {
	int dist = dist_left(x, y);
	for (int k = maxk - 1; k >= 0; k--) {
		if (step_left[x][k] < dist) {
			dist -= step_left[x][k];
			x = (x + n - step_left[x][k] % n) % n;
		}
	}
	return dist < k && height[x] < height[y];
}

int check_right(int x, int y) {
	int dist = dist_right(x, y);
	for (int k = maxk - 1; k >= 0; k--) {
		if (step_right[x][k] < dist) {
			dist -= step_right[x][k];
			x = (x + step_right[x][k]) % n;
		}
	}
	return dist < k && height[x] < height[y];
}

int compare_plants(int x, int y) {
	if (check_left(x, y) || check_right(x, y)) {
		return -1;
	}
	else if (check_left(y, x) || check_right(y, x)) {
		return 1;
	}
	else {
		return 0;
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 131 ms 4060 KB Output is correct
7 Correct 156 ms 9444 KB Output is correct
8 Correct 367 ms 48916 KB Output is correct
9 Correct 364 ms 48368 KB Output is correct
10 Correct 392 ms 48388 KB Output is correct
11 Correct 387 ms 48908 KB Output is correct
12 Correct 392 ms 48724 KB Output is correct
13 Correct 449 ms 53068 KB Output is correct
14 Correct 365 ms 43768 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 668 KB Output is correct
7 Correct 61 ms 4944 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 60 ms 4960 KB Output is correct
11 Correct 134 ms 4708 KB Output is correct
12 Correct 111 ms 4968 KB Output is correct
13 Correct 60 ms 5004 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 668 KB Output is correct
7 Correct 61 ms 4944 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 60 ms 4960 KB Output is correct
11 Correct 134 ms 4708 KB Output is correct
12 Correct 111 ms 4968 KB Output is correct
13 Correct 60 ms 5004 KB Output is correct
14 Correct 95 ms 8400 KB Output is correct
15 Runtime error 510 ms 96276 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 120 ms 4108 KB Output is correct
4 Correct 460 ms 44660 KB Output is correct
5 Correct 459 ms 42304 KB Output is correct
6 Correct 465 ms 41672 KB Output is correct
7 Correct 472 ms 41984 KB Output is correct
8 Runtime error 495 ms 92332 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 34 ms 1256 KB Output is correct
8 Correct 14 ms 1296 KB Output is correct
9 Correct 30 ms 1236 KB Output is correct
10 Correct 14 ms 1344 KB Output is correct
11 Correct 32 ms 1272 KB Output is correct
12 Correct 27 ms 1268 KB Output is correct
13 Correct 12 ms 1348 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 453 ms 43508 KB Output is correct
7 Correct 400 ms 43684 KB Output is correct
8 Correct 434 ms 44304 KB Output is correct
9 Runtime error 495 ms 94712 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 131 ms 4060 KB Output is correct
7 Correct 156 ms 9444 KB Output is correct
8 Correct 367 ms 48916 KB Output is correct
9 Correct 364 ms 48368 KB Output is correct
10 Correct 392 ms 48388 KB Output is correct
11 Correct 387 ms 48908 KB Output is correct
12 Correct 392 ms 48724 KB Output is correct
13 Correct 449 ms 53068 KB Output is correct
14 Correct 365 ms 43768 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 308 KB Output is correct
18 Correct 1 ms 312 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 3 ms 668 KB Output is correct
21 Correct 61 ms 4944 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 3 ms 596 KB Output is correct
24 Correct 60 ms 4960 KB Output is correct
25 Correct 134 ms 4708 KB Output is correct
26 Correct 111 ms 4968 KB Output is correct
27 Correct 60 ms 5004 KB Output is correct
28 Correct 95 ms 8400 KB Output is correct
29 Runtime error 510 ms 96276 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -