oj.uz

Submission #740431

# Submission time Handle Problem Language Result Execution time Memory
740431 2023-05-12T13:03:21 Z lohacho Comparing Plants (IOI20_plants) C++14
30 / 100
 1166 ms 78464 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) {
	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((y - now + n) % n < k && 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((now - y + n) % n < k && 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 120 ms 9460 KB Output is correct
7 Correct 159 ms 15224 KB Output is correct
8 Correct 539 ms 77388 KB Output is correct
9 Correct 565 ms 67788 KB Output is correct
10 Correct 598 ms 62580 KB Output is correct
11 Correct 607 ms 62028 KB Output is correct
12 Correct 612 ms 61940 KB Output is correct
13 Correct 576 ms 61868 KB Output is correct
14 Correct 723 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 3 ms 6612 KB Output is correct
3 Correct 3 ms 6544 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 7 ms 6996 KB Output is correct
7 Correct 107 ms 11084 KB Output is correct
8 Correct 5 ms 6612 KB Output is correct
9 Correct 7 ms 6996 KB Output is correct
10 Correct 104 ms 11140 KB Output is correct
11 Correct 92 ms 10876 KB Output is correct
12 Correct 153 ms 10980 KB Output is correct
13 Correct 104 ms 11164 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 3 ms 6612 KB Output is correct
3 Correct 3 ms 6544 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 7 ms 6996 KB Output is correct
7 Correct 107 ms 11084 KB Output is correct
8 Correct 5 ms 6612 KB Output is correct
9 Correct 7 ms 6996 KB Output is correct
10 Correct 104 ms 11140 KB Output is correct
11 Correct 92 ms 10876 KB Output is correct
12 Correct 153 ms 10980 KB Output is correct
13 Correct 104 ms 11164 KB Output is correct
14 Correct 162 ms 16332 KB Output is correct
15 Incorrect 1166 ms 77508 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 109 ms 10104 KB Output is correct
4 Correct 788 ms 78464 KB Output is correct
5 Correct 828 ms 77504 KB Output is correct
6 Correct 1034 ms 77516 KB Output is correct
7 Correct 1088 ms 77516 KB Output is correct
8 Incorrect 1144 ms 77524 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 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 7 ms 6612 KB Output is correct
7 Correct 31 ms 7240 KB Output is correct
8 Correct 25 ms 7256 KB Output is correct
9 Correct 28 ms 7252 KB Output is correct
10 Correct 25 ms 7252 KB Output is correct
11 Correct 34 ms 7244 KB Output is correct
12 Correct 29 ms 7284 KB Output is correct
13 Correct 23 ms 7300 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 3 ms 6516 KB Output is correct
3 Correct 3 ms 6612 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Correct 6 ms 6912 KB Output is correct
6 Correct 736 ms 77648 KB Output is correct
7 Correct 949 ms 77556 KB Output is correct
8 Correct 930 ms 77512 KB Output is correct
9 Incorrect 1067 ms 77612 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 120 ms 9460 KB Output is correct
7 Correct 159 ms 15224 KB Output is correct
8 Correct 539 ms 77388 KB Output is correct
9 Correct 565 ms 67788 KB Output is correct
10 Correct 598 ms 62580 KB Output is correct
11 Correct 607 ms 62028 KB Output is correct
12 Correct 612 ms 61940 KB Output is correct
13 Correct 576 ms 61868 KB Output is correct
14 Correct 723 ms 61828 KB Output is correct
15 Correct 3 ms 6612 KB Output is correct
16 Correct 3 ms 6612 KB Output is correct
17 Correct 3 ms 6544 KB Output is correct
18 Correct 3 ms 6612 KB Output is correct
19 Correct 3 ms 6612 KB Output is correct
20 Correct 7 ms 6996 KB Output is correct
21 Correct 107 ms 11084 KB Output is correct
22 Correct 5 ms 6612 KB Output is correct
23 Correct 7 ms 6996 KB Output is correct
24 Correct 104 ms 11140 KB Output is correct
25 Correct 92 ms 10876 KB Output is correct
26 Correct 153 ms 10980 KB Output is correct
27 Correct 104 ms 11164 KB Output is correct
28 Correct 162 ms 16332 KB Output is correct
29 Incorrect 1166 ms 77508 KB Output isn't correct
30 Halted 0 ms 0 KB -