oj.uz

Submission #770869

# Submission time Handle Problem Language Result Execution time Memory
770869 2023-07-02T05:25:41 Z SanguineChameleon Comparing Plants (IOI20_plants) C++17
32 / 100
 200 ms 14288 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 20;
const int inf = 1e9 + 20;
int a[maxn];
pair<int, int> tree[maxn * 4];
int lazy[maxn * 4];
int pos[maxn];
int dp_left[maxn];
int dp_right[maxn];
int n, k;

bool cmp(pair<int, int> p1, pair<int, int> p2) {
	if (p1.first != p2.first) {
		return p1.first < p2.first;
	}
	else if (p1.second < p2.second && p2.second - p1.second + 1 <= k) {
		return true;
	}
	else if (p1.second > p2.second && n - (p1.second - p2.second - 1) <= k) {
		return true;
	}
	else {
		return false;
	}
}

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tree[id] = make_pair(a[lt], 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], cmp);
}

void update(int id, int lt, int rt, int ql, int qr, int add) {
	if (lt == ql && rt == qr) {
		tree[id].first += add;
		lazy[id] += add;
		return;
	}
	tree[id * 2].first += lazy[id];
	lazy[id * 2] += lazy[id];
	tree[id * 2 + 1].first += 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], cmp);
}

void init(int _k, vector<int> _a) {
	n = _a.size();
	k = _k;
	for (int i = 0; i < n; i++) {
		a[i] = k - 1 - _a[i];
	}
	if (k == 2) {
		for (int i = 0; i < n; i++) {
			if (a[i] == 0) {
				dp_right[i] = i;
				for (int j = (i + n - 1) % n; j != i; j = (j + n - 1) % n) {
					dp_right[j] = (a[j] ? dp_right[(j + 1) % n] : j);
				}
				break;
			}
		}
		for (int i = 0; i < n; i++) {
			if (a[(i + n - 1) % n] == 1) {
				dp_left[i] = i;
				for (int j = (i + 1) % n; j != i; j = (j + 1) % n) {
					dp_left[j] = (!a[(j + n - 1) % n] ? dp_left[(j + n - 1) % n] : j);
				}
				break;
			}
		}
	}
	else {
		build(1, 0, n - 1);
		for (int i = 0; i < n; i++) {
			int rt = tree[1].second;
			int lt = (rt + n - (k - 1)) % n;
			pos[rt] = i;
			update(1, 0, n - 1, rt, rt, inf);
			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);
			}
		}
	}
	return;
}

bool check(int x, int y) {
	if (dp_left[x] == dp_right[x]) {
		return (dp_left[x] != x);
	}
	else if (dp_left[x] < dp_right[x]) {
		return dp_left[x] <= y && y <= dp_right[x];
	}
	else {
		return (y >= dp_left[x] || y <= dp_right[x]);
	}
}

int compare_plants(int x, int y) {
	if (k == 2) {
		if (check(x, y)) {
			return 1;
		}
		else if (check(y, x)) {
			return -1;
		}
		else {
			return 0;
		}
	}
	else {
		return (pos[x] > pos[y] ? 1 : -1);
	}
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 316 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 40 ms 4048 KB Output is correct
7 Correct 49 ms 5672 KB Output is correct
8 Correct 70 ms 9440 KB Output is correct
9 Correct 61 ms 9456 KB Output is correct
10 Correct 60 ms 9456 KB Output is correct
11 Correct 70 ms 9408 KB Output is correct
12 Correct 63 ms 9544 KB Output is correct
13 Correct 60 ms 9436 KB Output is correct
14 Correct 58 ms 9420 KB Output is correct

Subtask #2
14.0 / 14.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 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 2 ms 468 KB Output is correct
7 Correct 46 ms 4956 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 452 KB Output is correct
10 Correct 44 ms 4820 KB Output is correct
11 Correct 42 ms 4720 KB Output is correct
12 Correct 43 ms 4844 KB Output is correct
13 Correct 44 ms 4868 KB Output is correct

Subtask #3
13.0 / 13.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 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 2 ms 468 KB Output is correct
7 Correct 46 ms 4956 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 2 ms 452 KB Output is correct
10 Correct 44 ms 4820 KB Output is correct
11 Correct 42 ms 4720 KB Output is correct
12 Correct 43 ms 4844 KB Output is correct
13 Correct 44 ms 4868 KB Output is correct
14 Correct 56 ms 5564 KB Output is correct
15 Correct 189 ms 13400 KB Output is correct
16 Correct 55 ms 6244 KB Output is correct
17 Correct 187 ms 14188 KB Output is correct
18 Correct 159 ms 14288 KB Output is correct
19 Correct 160 ms 14244 KB Output is correct
20 Correct 200 ms 14264 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 44 ms 4632 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 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 1 ms 316 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 40 ms 4048 KB Output is correct
7 Correct 49 ms 5672 KB Output is correct
8 Correct 70 ms 9440 KB Output is correct
9 Correct 61 ms 9456 KB Output is correct
10 Correct 60 ms 9456 KB Output is correct
11 Correct 70 ms 9408 KB Output is correct
12 Correct 63 ms 9544 KB Output is correct
13 Correct 60 ms 9436 KB Output is correct
14 Correct 58 ms 9420 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 2 ms 468 KB Output is correct
21 Correct 46 ms 4956 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 2 ms 452 KB Output is correct
24 Correct 44 ms 4820 KB Output is correct
25 Correct 42 ms 4720 KB Output is correct
26 Correct 43 ms 4844 KB Output is correct
27 Correct 44 ms 4868 KB Output is correct
28 Correct 56 ms 5564 KB Output is correct
29 Correct 189 ms 13400 KB Output is correct
30 Correct 55 ms 6244 KB Output is correct
31 Correct 187 ms 14188 KB Output is correct
32 Correct 159 ms 14288 KB Output is correct
33 Correct 160 ms 14244 KB Output is correct
34 Correct 200 ms 14264 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Incorrect 44 ms 4632 KB Output isn't correct
38 Halted 0 ms 0 KB -