Submission #740425

#	Time	Username	Problem	Language	Result	Execution time	Memory
740425		lohacho	Comparing Plants (IOI20_plants)	C++14	30 / 100	1382 ms	81424 KiB

plants

#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 (stderr)

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 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25