oj.uz

Submission #770970

# Submission time Handle Problem Language Result Execution time Memory
770970 2023-07-02T08:35:25 Z SanguineChameleon Comparing Plants (IOI20_plants) C++17
30 / 100
 531 ms 95628 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], -1));
		step_right[prv][0] = (it == heights.end() ? 0 : dist_right(prv, it->second));
		it = heights.upper_bound(make_pair(height[nxt], -1));
		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 0 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 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 131 ms 3212 KB Output is correct
7 Correct 155 ms 7756 KB Output is correct
8 Correct 368 ms 46704 KB Output is correct
9 Correct 360 ms 46064 KB Output is correct
10 Correct 359 ms 46200 KB Output is correct
11 Correct 382 ms 46632 KB Output is correct
12 Correct 405 ms 46476 KB Output is correct
13 Correct 416 ms 50888 KB Output is correct
14 Correct 377 ms 41568 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 60 ms 4556 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 67 ms 4784 KB Output is correct
11 Correct 134 ms 4364 KB Output is correct
12 Correct 96 ms 4564 KB Output is correct
13 Correct 59 ms 4620 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 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 1 ms 340 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 60 ms 4556 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 67 ms 4784 KB Output is correct
11 Correct 134 ms 4364 KB Output is correct
12 Correct 96 ms 4564 KB Output is correct
13 Correct 59 ms 4620 KB Output is correct
14 Correct 92 ms 7948 KB Output is correct
15 Runtime error 507 ms 95628 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 0 ms 340 KB Output is correct
3 Correct 121 ms 3744 KB Output is correct
4 Correct 464 ms 44524 KB Output is correct
5 Correct 452 ms 42244 KB Output is correct
6 Correct 467 ms 41540 KB Output is correct
7 Correct 531 ms 41940 KB Output is correct
8 Runtime error 501 ms 92128 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 0 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 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 34 ms 1188 KB Output is correct
8 Correct 13 ms 1236 KB Output is correct
9 Correct 26 ms 1232 KB Output is correct
10 Correct 14 ms 1300 KB Output is correct
11 Correct 32 ms 1188 KB Output is correct
12 Correct 27 ms 1184 KB Output is correct
13 Correct 13 ms 1236 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 1 ms 340 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 2 ms 444 KB Output is correct
6 Correct 453 ms 41564 KB Output is correct
7 Correct 382 ms 41464 KB Output is correct
8 Correct 426 ms 41952 KB Output is correct
9 Runtime error 491 ms 92312 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 0 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 340 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 131 ms 3212 KB Output is correct
7 Correct 155 ms 7756 KB Output is correct
8 Correct 368 ms 46704 KB Output is correct
9 Correct 360 ms 46064 KB Output is correct
10 Correct 359 ms 46200 KB Output is correct
11 Correct 382 ms 46632 KB Output is correct
12 Correct 405 ms 46476 KB Output is correct
13 Correct 416 ms 50888 KB Output is correct
14 Correct 377 ms 41568 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 312 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 3 ms 596 KB Output is correct
21 Correct 60 ms 4556 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 3 ms 596 KB Output is correct
24 Correct 67 ms 4784 KB Output is correct
25 Correct 134 ms 4364 KB Output is correct
26 Correct 96 ms 4564 KB Output is correct
27 Correct 59 ms 4620 KB Output is correct
28 Correct 92 ms 7948 KB Output is correct
29 Runtime error 507 ms 95628 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -