Submission #373423

#	Time	Username	Problem	Language	Result	Execution time	Memory
373423		pit4h	Comparing Plants (IOI20_plants)	C++14	100 / 100	1682 ms	89964 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using pii = pair<int, int>;

const int MAXN = 2e5+1, base = (1<<18);
int n, k, when[MAXN], nr;
int ptr[MAXN], ptrr[MAXN];
vector<int> R;

pii tree_max[2*base+1];
void upd(int x) {
	pii val = mp(when[x], x);
	x+=base;
	while(x) {
		tree_max[x] = max(tree_max[x], val);	
		x/=2;
	}
}
pii find_max(int l, int r) {
	if(l>r) {
		return max(find_max(l, n-1), find_max(0, r));
	}
	l+=base, r+=base;
	pii res = tree_max[l];
	if(l!=r) res = max(res, tree_max[r]);
	while(l/2 != r/2) {
		if(l%2==0) res = max(res, tree_max[l+1]);
		if(r%2==1) res = max(res, tree_max[r-1]);
		l /= 2;
		r /= 2;
	}
	return res;
}

int tree[2*base+1], push[2*base+1];
void ADD(int id, int val) {
	tree[id] += val;
	push[id] += val;
}
void add(int l, int r, int val, int id=1, int rl=0, int rr=base-1) {
	if(l>r) {
		add(l, n-1, val), add(0, r, val);
		return;
	}
	if(l>rr || r<rl) return;
	if(l<=rl && r>=rr) {
		ADD(id, val);
		return;
	}
	ADD(id*2, push[id]), ADD(id*2+1, push[id]);
	push[id] = 0;
	add(l, r, val, id*2, rl, (rl+rr)/2), add(l, r, val, id*2+1, (rl+rr)/2+1, rr);
	tree[id] = min(tree[id*2], tree[id*2+1]);
}
int find_closest_zero(int l, int r, int id=1, int rl=0, int rr=base-1) {
	if(l>rr || r<rl || tree[id]>0) return -1;
	if(rl==rr) {
		return rl;
	}

	ADD(id*2, push[id]), ADD(id*2+1, push[id]);
	push[id] = 0;

	int rs = find_closest_zero(l, r, id*2+1, (rl+rr)/2+1, rr);
	if(rs!=-1) return rs;
	return find_closest_zero(l, r, id*2, rl, (rl+rr)/2);
}
int clw_dist(int x, int y) {
	return (x<=y)? y-x: n-(x-y);
}

void solve(int x) {
	//cerr<<"solve("<<x<<")\n";
	while(true) {
		int prv = -1;
		if(x>0) {
			prv = find_closest_zero(0, x-1);
		}
		if(x<n-1 && prv==-1) {
			prv = find_closest_zero(x+1, n-1);
		}
		if(prv != -1 && clw_dist(prv, x) < k) {
			//cerr<<"->";
			solve(prv);
		}
		else {
			break;
		}
	}
	when[x] = ++nr;
	ptr[x] = find_max((x+1)%n, (x+k-1)%n).second;
	ptrr[x] = find_max((x-(k-1)+n)%n, (x-1+n)%n).second;

	add((x-(k-1)+n)%n, (x-1+n)%n, -1);
	add(x, x, n);
	upd(x);
}

void prep_jumps();
void init(int _k, vector<int> _r) {
	k = _k, R = _r, n = R.size();	

	for(int i=0; i<2*base; ++i) {
		tree_max[i] = mp(-1, -1);
	}

	for(int i=0; i<n; ++i) {
		tree[i+base] = R[i];
	}
	for(int i=base-1; i>=1; --i) {
		tree[i] = min(tree[i*2], tree[i*2+1]);
	}

	while(nr < n) {
		int cur = find_closest_zero(0, n-1);	
		assert(cur != -1);
		solve(cur);
	}
	prep_jumps();
}

const int L = 19;
pii jump[L][MAXN], jumpr[L][MAXN];
void prep_jumps() {
	for(int i=0; i<n; ++i) {
		jump[0][i] = mp(ptr[i], clw_dist(i, ptr[i]));
		jumpr[0][i] = mp(ptrr[i], clw_dist(ptrr[i], i));
	}
	for(int l=1; l<L; ++l) {
		for(int i=0; i<n; ++i) {
			if(jump[l-1][i].st != -1) {
				jump[l][i] = jump[l-1][jump[l-1][i].st];
				jump[l][i].nd += jump[l-1][i].nd;
				jump[l][i].nd = min(n, jump[l][i].nd);
			}
			else {
				jump[l][i] = mp(-1, 1);
			}

			if(jumpr[l-1][i].st != -1) {
				jumpr[l][i] = jumpr[l-1][jumpr[l-1][i].st];
				jumpr[l][i].nd += jumpr[l-1][i].nd;
				jumpr[l][i].nd = min(n, jumpr[l][i].nd);
			}
			else {
				jumpr[l][i] = mp(-1, 1);
			}
		}
	}
}
bool is_bigger(int _x, int y) {
	int x = _x;
	for(int l=L-1; l>=0; --l) {
		if(jump[l][x].st!=-1 && jump[l][x].nd <= clw_dist(x, y)) {
			x = jump[l][x].st;
		}
	}
	if(clw_dist(x, y)<k && when[x] >= when[y]) return true;

	x = _x;
	for(int l=L-1; l>=0; --l) {
		if(jumpr[l][x].st!=-1 && jumpr[l][x].nd <= clw_dist(y, x)) {
			x = jumpr[l][x].st;
		}
	}
	if(clw_dist(y, x)<k  && when[x] >= when[y]) return true;
	return false;
}

int compare_plants(int x, int y) {
	if(is_bigger(x, y)) return -1;
	if(is_bigger(y, x)) return 1;
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25