oj.uz

Submission #740421

# Submission time Handle Problem Language Result Execution time Memory
740421 2023-05-12T12:46:30 Z lohacho Comparing Plants (IOI20_plants) C++14
5 / 100
 667 ms 49116 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], 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);
		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);

		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]);
			L[i][j] = (L[i][j - 1] == -1 ? -1 : L[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 && cr(x, y, R[now][j]) == 1){
				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 && cr(x, y, L[now][j]) == -1){
				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 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6584 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6584 KB Output is correct
6 Correct 71 ms 10340 KB Output is correct
7 Correct 126 ms 15232 KB Output is correct
8 Correct 505 ms 49116 KB Output is correct
9 Correct 514 ms 49104 KB Output is correct
10 Correct 603 ms 49020 KB Output is correct
11 Correct 582 ms 49040 KB Output is correct
12 Correct 575 ms 49028 KB Output is correct
13 Correct 553 ms 49108 KB Output is correct
14 Correct 667 ms 49052 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6588 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Incorrect 4 ms 6576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6588 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6612 KB Output is correct
5 Incorrect 4 ms 6576 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 4 ms 6588 KB Output is correct
3 Incorrect 89 ms 11484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6580 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6592 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6584 KB Output is correct
6 Correct 5 ms 6612 KB Output is correct
7 Correct 21 ms 7568 KB Output is correct
8 Incorrect 23 ms 7496 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6584 KB Output is correct
3 Correct 3 ms 6588 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Incorrect 5 ms 6724 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6584 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6584 KB Output is correct
6 Correct 71 ms 10340 KB Output is correct
7 Correct 126 ms 15232 KB Output is correct
8 Correct 505 ms 49116 KB Output is correct
9 Correct 514 ms 49104 KB Output is correct
10 Correct 603 ms 49020 KB Output is correct
11 Correct 582 ms 49040 KB Output is correct
12 Correct 575 ms 49028 KB Output is correct
13 Correct 553 ms 49108 KB Output is correct
14 Correct 667 ms 49052 KB Output is correct
15 Correct 3 ms 6484 KB Output is correct
16 Correct 3 ms 6588 KB Output is correct
17 Correct 3 ms 6484 KB Output is correct
18 Correct 3 ms 6612 KB Output is correct
19 Incorrect 4 ms 6576 KB Output isn't correct
20 Halted 0 ms 0 KB -