oj.uz

Submission #740425

# Submission time Handle Problem Language Result Execution time Memory
740425 2023-05-12T12:57:59 Z lohacho Comparing Plants (IOI20_plants) C++14
30 / 100
 1382 ms 81424 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

const int NS = (int)2e5 + 4;
int mn[NS * 4 + 4], id[NS * 4 + 4], lazy[NS * 4 + 4];
int k;
vector<int> r;
int ans[NS];
int n;
int L[NS][20], R[NS][20], LD[NS][20], RD[NS][20], bk[NS];

void update(int x, int s, int e){
	if(!lazy[x] || s == e) return;
	lazy[x * 2] += lazy[x], mn[x * 2] += lazy[x];
	lazy[x * 2 + 1] += lazy[x], mn[x * 2 + 1] += lazy[x];
	lazy[x] = 0;
}

void push(int x, int s, int e, int ps, int pe, int val){
	if(pe < s || ps > e || ps > pe){
		return;
	}
	if(ps <= s && pe >= e){
		if(s == e) id[x] = s;
		mn[x] += val;
		lazy[x] += val;
		return;
	}
	update(x, s, e);
	int m = s + e >> 1;
	push(x * 2, s, m, ps, pe, val);
	push(x * 2 + 1, m + 1, e, ps, pe, val);
	if(mn[x * 2] <= mn[x * 2 + 1]){
		mn[x] = mn[x * 2], id[x] = id[x * 2];
	}
	else{
		mn[x] = mn[x * 2 + 1], id[x] = id[x * 2 + 1];
	}
}

pair<int, int> get(int x, int s, int e, int fs, int fe){
	if(fe < s || fs > e || fs > fe){
		return {(int)1e9, (int)1e9};
	}
	if(fs <= s && fe >= e){
		return {mn[x], id[x]};
	}
	update(x, s, e);
	int m = s + e >> 1;
	return min(get(x * 2, s, m, fs, fe), get(x * 2 + 1, m + 1, e, fs, fe));
}

void init(int K, std::vector<int> RR) {
	k = K;
	r = RR;
	n = (int)r.size();
	for(int i = 0; i < n; ++i){
		push(1, 0, n - 1, i, i, r[i]);
	}
	for(int i = n - 1; i >= 0;){
		auto rv = get(1, 0, n - 1, 0, n - 1);
		auto sol = [&](auto&&self, int now)->void{
			while(true){
				rv = get(1, 0, n - 1, now - k + 1, now - 1);
				rv = min(rv, get(1, 0, n - 1, n - (k - now - 1), n - 1));
				if(rv.first == 0){
					self(self, rv.second);
				}
				else{
					break;
				}
			}
			ans[now] = i--;
			bk[ans[now]] = now;
			push(1, 0, n - 1, now - k + 1, now, -1);
			push(1, 0, n - 1, n - (k - now) + 1, n - 1, -1);
			push(1, 0, n - 1, now, now, (int)1e9);
		};
		sol(sol, rv.second);
	}

	memset(mn, 0, sizeof(mn));
	memset(lazy, 0, sizeof(lazy));
	for(int i = 0; i < n; ++i){
		int now = bk[i];
		auto rv = min(get(1, 0, n - 1, now - k + 1, now - 1), get(1, 0, n - 1, n - (k - now - 1), n - 1));
		L[now][0] = (rv.first ? rv.second : -1);
		if(L[now][0] != -1) LD[now][0] = (now - L[now][0] + n) % n;

		rv = min(get(1, 0, n - 1, now + 1, now + k - 1), get(1, 0, n - 1, 0, k - (n - now) - 1));
		R[now][0] = (rv.first ? rv.second : -1);
		if(R[now][0] != -1) RD[now][0] = (R[now][0] - now + n) % n;

		push(1, 0, n - 1, now, now, -i - 1);
	}

	for(int j = 1; j < 20; ++j){
		for(int i = 0; i < n; ++i){
			R[i][j] = (R[i][j - 1] == -1 ? -1 : R[R[i][j - 1]][j - 1]);
			if(R[i][j] != -1) RD[i][j] = RD[i][j - 1] + RD[R[i][j - 1]][j - 1];
			L[i][j] = (L[i][j - 1] == -1 ? -1 : L[L[i][j - 1]][j - 1]);
			if(L[i][j] != -1) LD[i][j] = LD[i][j - 1] + LD[L[i][j - 1]][j - 1];
		}
	}
}

int compare_plants(int x, int y) {
	auto cr = [&](int x, int y, int z){
		int gop = (z > min(x, y) && z < max(x, y));
		if(!gop && (z < min(x, y) || z > max(x, y))) gop = -1;
		return ((x < y ? 1 : -1) * gop);
	};
	for(int i = 0; i < 2; ++i){
		int now = x;
		for(int j = 19; j >= 0; --j){
			if(R[now][j] != -1 && RD[now][j] < (y - now + n) % n){
				now = R[now][j];
			}
		}
		if(cr(now, y, (now + k - 1) % n) != 1 && ans[now] > ans[y]){
			return (i ? -1 : 1);
		}

		now = x;
		for(int j = 19; j >= 0; --j){
			if(L[now][j] != -1 && LD[now][j] < (now - y + n) % n){
				now = L[now][j];
			}
		}
		if(cr(now, y, (now - k + 1 + n) % n) != -1 && ans[now] > ans[y]){
			return (i ? -1 : 1);
		}

		swap(x, y);
	}

	return 0;
}

Compilation message

plants.cpp: In function 'void push(int, int, int, int, int, int)':
plants.cpp:31:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |  int m = s + e >> 1;
      |          ~~^~~
plants.cpp: In function 'std::pair<int, int> get(int, int, int, int, int)':
plants.cpp:50:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |  int m = s + e >> 1;
      |          ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 75 ms 9332 KB Output is correct
7 Correct 140 ms 15288 KB Output is correct
8 Correct 587 ms 77524 KB Output is correct
9 Correct 593 ms 67804 KB Output is correct
10 Correct 605 ms 62788 KB Output is correct
11 Correct 639 ms 62052 KB Output is correct
12 Correct 654 ms 61812 KB Output is correct
13 Correct 574 ms 61932 KB Output is correct
14 Correct 743 ms 61828 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 8 ms 6980 KB Output is correct
7 Correct 98 ms 13004 KB Output is correct
8 Correct 5 ms 6720 KB Output is correct
9 Correct 7 ms 6948 KB Output is correct
10 Correct 108 ms 13004 KB Output is correct
11 Correct 89 ms 12748 KB Output is correct
12 Correct 121 ms 13020 KB Output is correct
13 Correct 95 ms 13044 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 8 ms 6980 KB Output is correct
7 Correct 98 ms 13004 KB Output is correct
8 Correct 5 ms 6720 KB Output is correct
9 Correct 7 ms 6948 KB Output is correct
10 Correct 108 ms 13004 KB Output is correct
11 Correct 89 ms 12748 KB Output is correct
12 Correct 121 ms 13020 KB Output is correct
13 Correct 95 ms 13044 KB Output is correct
14 Correct 164 ms 18532 KB Output is correct
15 Incorrect 1382 ms 81224 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 98 ms 10040 KB Output is correct
4 Correct 829 ms 81424 KB Output is correct
5 Correct 919 ms 80736 KB Output is correct
6 Correct 1332 ms 80836 KB Output is correct
7 Correct 1209 ms 81132 KB Output is correct
8 Incorrect 1346 ms 81176 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 4 ms 6612 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 5 ms 6672 KB Output is correct
6 Correct 5 ms 6652 KB Output is correct
7 Correct 32 ms 7252 KB Output is correct
8 Correct 24 ms 7272 KB Output is correct
9 Correct 22 ms 7564 KB Output is correct
10 Correct 23 ms 7564 KB Output is correct
11 Correct 24 ms 7652 KB Output is correct
12 Correct 26 ms 7612 KB Output is correct
13 Correct 20 ms 7612 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 5 ms 6868 KB Output is correct
6 Correct 740 ms 79680 KB Output is correct
7 Correct 943 ms 79900 KB Output is correct
8 Correct 990 ms 80156 KB Output is correct
9 Incorrect 1107 ms 80516 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 75 ms 9332 KB Output is correct
7 Correct 140 ms 15288 KB Output is correct
8 Correct 587 ms 77524 KB Output is correct
9 Correct 593 ms 67804 KB Output is correct
10 Correct 605 ms 62788 KB Output is correct
11 Correct 639 ms 62052 KB Output is correct
12 Correct 654 ms 61812 KB Output is correct
13 Correct 574 ms 61932 KB Output is correct
14 Correct 743 ms 61828 KB Output is correct
15 Correct 3 ms 6612 KB Output is correct
16 Correct 4 ms 6612 KB Output is correct
17 Correct 4 ms 6612 KB Output is correct
18 Correct 4 ms 6612 KB Output is correct
19 Correct 3 ms 6612 KB Output is correct
20 Correct 8 ms 6980 KB Output is correct
21 Correct 98 ms 13004 KB Output is correct
22 Correct 5 ms 6720 KB Output is correct
23 Correct 7 ms 6948 KB Output is correct
24 Correct 108 ms 13004 KB Output is correct
25 Correct 89 ms 12748 KB Output is correct
26 Correct 121 ms 13020 KB Output is correct
27 Correct 95 ms 13044 KB Output is correct
28 Correct 164 ms 18532 KB Output is correct
29 Incorrect 1382 ms 81224 KB Output isn't correct
30 Halted 0 ms 0 KB -