Submission #373416

#	Time	Username	Problem	Language	Result	Execution time	Memory
373416		pit4h	Comparing Plants (IOI20_plants)	C++14	44 / 100	938 ms	30340 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 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);
	}
}

bool is_bigger(int _x, int y) {
	int x = _x;
	return when[x] > when[y];
	while(x!=-1 && clw_dist(x, y)>=k) {
		x = ptr[x];	
	}
	if(x!=-1 && when[x] >= when[y]) return true;

	x = _x;
	while(x != -1 && clw_dist(y, x)>=k) {
		x = ptrr[x];
	}
	if(x!=-1 && 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: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25