oj.uz

Submission #770976

# Submission time Handle Problem Language Result Execution time Memory
770976 2023-07-02T08:39:41 Z SanguineChameleon Comparing Plants (IOI20_plants) C++17
44 / 100
 606 ms 81912 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];
long long step_left[maxn][maxk];
long long 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[(step_right[i][k - 1] + i) % n][k - 1];
			step_left[i][k] = step_left[i][k - 1] + step_left[(n - step_left[i][k - 1] % n + i) % 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) {
	return height[x] > height[y] ? 1 : -1;
	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
0 / 5.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 340 KB Output is correct
4 Incorrect 0 ms 340 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 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 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 724 KB Output is correct
7 Correct 49 ms 5044 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 47 ms 5036 KB Output is correct
11 Correct 45 ms 4964 KB Output is correct
12 Correct 44 ms 5116 KB Output is correct
13 Correct 48 ms 5080 KB Output is correct

Subtask #3
13.0 / 13.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 1 ms 340 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 724 KB Output is correct
7 Correct 49 ms 5044 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 47 ms 5036 KB Output is correct
11 Correct 45 ms 4964 KB Output is correct
12 Correct 44 ms 5116 KB Output is correct
13 Correct 48 ms 5080 KB Output is correct
14 Correct 78 ms 10700 KB Output is correct
15 Correct 526 ms 78324 KB Output is correct
16 Correct 77 ms 10804 KB Output is correct
17 Correct 509 ms 78400 KB Output is correct
18 Correct 367 ms 77332 KB Output is correct
19 Correct 322 ms 77224 KB Output is correct
20 Correct 606 ms 81880 KB Output is correct

Subtask #4
17.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 42 ms 3828 KB Output is correct
4 Correct 282 ms 75660 KB Output is correct
5 Correct 317 ms 73208 KB Output is correct
6 Correct 362 ms 72560 KB Output is correct
7 Correct 407 ms 72992 KB Output is correct
8 Correct 554 ms 76756 KB Output is correct
9 Correct 305 ms 74840 KB Output is correct
10 Correct 298 ms 73208 KB Output is correct
11 Correct 235 ms 81912 KB Output is correct
12 Correct 247 ms 72408 KB Output is correct
13 Correct 329 ms 79108 KB Output is correct

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