oj.uz

Submission #770972

# Submission time Handle Problem Language Result Execution time Memory
770972 2023-07-02T08:36:55 Z SanguineChameleon Comparing Plants (IOI20_plants) C++17
44 / 100
 251 ms 20776 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 212 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 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 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 45 ms 3328 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 44 ms 3276 KB Output is correct
11 Correct 42 ms 3332 KB Output is correct
12 Correct 45 ms 3412 KB Output is correct
13 Correct 47 ms 3360 KB Output is correct

Subtask #3
13.0 / 13.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 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 45 ms 3328 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 44 ms 3276 KB Output is correct
11 Correct 42 ms 3332 KB Output is correct
12 Correct 45 ms 3412 KB Output is correct
13 Correct 47 ms 3360 KB Output is correct
14 Correct 55 ms 3896 KB Output is correct
15 Correct 230 ms 9908 KB Output is correct
16 Correct 63 ms 4808 KB Output is correct
17 Correct 251 ms 11448 KB Output is correct
18 Correct 199 ms 16040 KB Output is correct
19 Correct 169 ms 11384 KB Output is correct
20 Correct 217 ms 11404 KB Output is correct

Subtask #4
17.0 / 17.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 43 ms 3128 KB Output is correct
4 Correct 153 ms 12936 KB Output is correct
5 Correct 182 ms 10484 KB Output is correct
6 Correct 214 ms 9980 KB Output is correct
7 Correct 229 ms 9912 KB Output is correct
8 Correct 213 ms 9844 KB Output is correct
9 Correct 195 ms 12948 KB Output is correct
10 Correct 191 ms 11624 KB Output is correct
11 Correct 169 ms 20776 KB Output is correct
12 Correct 155 ms 11736 KB Output is correct
13 Correct 201 ms 18476 KB Output is correct

Subtask #5
0 / 11.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 Incorrect 1 ms 316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -