oj.uz

Submission #770975

# Submission time Handle Problem Language Result Execution time Memory
770975 2023-07-02T08:38:02 Z SanguineChameleon Comparing Plants (IOI20_plants) C++17
44 / 100
 409 ms 50576 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) {
	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 1 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 0 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 2 ms 596 KB Output is correct
7 Correct 46 ms 4268 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 43 ms 4296 KB Output is correct
11 Correct 42 ms 4096 KB Output is correct
12 Correct 41 ms 4348 KB Output is correct
13 Correct 44 ms 4336 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 0 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 2 ms 596 KB Output is correct
7 Correct 46 ms 4268 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 43 ms 4296 KB Output is correct
11 Correct 42 ms 4096 KB Output is correct
12 Correct 41 ms 4348 KB Output is correct
13 Correct 44 ms 4336 KB Output is correct
14 Correct 64 ms 7568 KB Output is correct
15 Correct 409 ms 46944 KB Output is correct
16 Correct 63 ms 7580 KB Output is correct
17 Correct 389 ms 46908 KB Output is correct
18 Correct 262 ms 45820 KB Output is correct
19 Correct 243 ms 45936 KB Output is correct
20 Correct 388 ms 50564 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 39 ms 3576 KB Output is correct
4 Correct 183 ms 44272 KB Output is correct
5 Correct 222 ms 41828 KB Output is correct
6 Correct 255 ms 41212 KB Output is correct
7 Correct 365 ms 41676 KB Output is correct
8 Correct 365 ms 45336 KB Output is correct
9 Correct 210 ms 43468 KB Output is correct
10 Correct 211 ms 41908 KB Output is correct
11 Correct 157 ms 50576 KB Output is correct
12 Correct 169 ms 41224 KB Output is correct
13 Correct 247 ms 47724 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 1 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 -