oj.uz

Submission #740428

# Submission time Handle Problem Language Result Execution time Memory
740428 2023-05-12T13:00:04 Z lohacho Comparing Plants (IOI20_plants) C++14
14 / 100
 1080 ms 155320 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);
	}

	assert(0);

	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
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 4 ms 6612 KB Output is correct
4 Runtime error 10 ms 13140 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

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 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 6996 KB Output is correct
7 Correct 90 ms 11180 KB Output is correct
8 Correct 6 ms 6612 KB Output is correct
9 Correct 7 ms 6996 KB Output is correct
10 Correct 92 ms 11140 KB Output is correct
11 Correct 77 ms 10828 KB Output is correct
12 Correct 125 ms 11004 KB Output is correct
13 Correct 91 ms 11068 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 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 6996 KB Output is correct
7 Correct 90 ms 11180 KB Output is correct
8 Correct 6 ms 6612 KB Output is correct
9 Correct 7 ms 6996 KB Output is correct
10 Correct 92 ms 11140 KB Output is correct
11 Correct 77 ms 10828 KB Output is correct
12 Correct 125 ms 11004 KB Output is correct
13 Correct 91 ms 11068 KB Output is correct
14 Correct 151 ms 16332 KB Output is correct
15 Runtime error 1076 ms 155316 KB Execution killed with signal 6
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 81 ms 10092 KB Output is correct
4 Correct 843 ms 78524 KB Output is correct
5 Correct 836 ms 77636 KB Output is correct
6 Correct 1044 ms 77524 KB Output is correct
7 Correct 1080 ms 77568 KB Output is correct
8 Runtime error 976 ms 155320 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #5
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 Runtime error 10 ms 13140 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6612 KB Output is correct
2 Correct 3 ms 6612 KB Output is correct
3 Runtime error 9 ms 13224 KB Execution killed with signal 6
4 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 4 ms 6612 KB Output is correct
4 Runtime error 10 ms 13140 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -