Submission #1062984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062984		Itamar	Comparing Plants (IOI20_plants)	C++14	0 / 100	4094 ms	348 KiB

plants

#include<vector>
#define vi vector<int>
using namespace std;
#include<queue>
#include <set>
const int siz = 2e5+2;
int ans[siz];
int N,K;
vi R;
int dis(int a, int b){ // oriented
	if(b > a)return b-a;
	return b-a+K;
}
queue<int> q;

struct node{
	int l,r,mid,minir,plus;
	node* sl,*sr;
	node(int li, int ri){
		l = li, r = ri, mid = (l+r)/2,plus=0;
		if(l<r){
			sl = new node(l,mid);
			sr = new node(mid+1,r);
			minir = min(sl->minir,sr->minir);
		}else{
			minir = R[l];
		}
	}
	void push(){
		if(l==r)return;
		sl->minir+=plus;
		sr->minir+=plus;
		sl->plus+=plus;
		sr->plus+=plus;
		plus=0;
	}
	void update(int a, int b, int p){
		push();
		if(r < a || l > b)return;
		if(a <= l && b >= r){
			minir+=p;
			plus+=p;
		}else{
			sl->update(a,b,p);
			sr->update(a,b,p);
			minir = min(sl->minir,sr->minir);
		}
	}
	int find(){
     	push();
		if(l==r){
			if(minir<=0){
				update(l,l,1e9-minir);
				return l;
			}
			else return 1e9;
		}
		if(sl->minir<=0){
			return sl->find();
		}
		else return sr->find();
	}
};
set<int> s;
node* seg;
bool check(int i){
	auto it = s.find(i);
	if(it == s.end())return 0;
	auto it2 = it;
	if(it2!=s.begin())it2--;
	else it2 =  --s.end();
	if(it2 == s.end() || dis(*it2,i)>=K ){
		return 1;
	}
	else{
		q.push(i);
		return 0;
	}
}
void ins(int i){ // he now has r[i]=0
	//auto it = s.find(i);
	s.insert(i);
	//check(i);
}
int mod(int i){
	return (i+N)%N;
}
void er(int i){ // i was considered as a maximum
	auto it = s.find(i);
	if(i>=K-1){
		seg->update(i-K+1,i,-1);
	}else{
		seg->update(0,i,-1);
		seg->update(mod(i-K+1),N-1,-1);
	}
	auto it1 = it, it2 = it;
	it2++;
	s.erase(i);
	if(it2 == s.end())it2 = s.begin();
}
void init(int k, std::vector<int> r) {
	N = r.size(), K = k, R = r;
	 seg = new node(0,N-1);
	
	while(true){
		int f = seg->find();
		if(f==1e9)break;
		ins(f);
	}
	for(int i = 0; i < N; i++)if(r[i]==0){
		q.push(i);
	}
	int it = 0;
	vi vis(N);
	while(!q.empty()){
		int i = q.front();
		q.pop();
		if(vis[i])continue;
		if(check(i)==0)continue;
		vis[i]=1;
		er(i);
		ans[i]=it;
		it++;
		while(true){
		int f = seg->find();
		if(f==1e9)break;
		ins(f);
		q.push(f);
		}
	}
}

int compare_plants(int x, int y) {
	if(ans[x]<ans[y])return 1;
	return -1;
}

Compilation message (stderr)

plants.cpp: In function 'void er(int)':
plants.cpp:96:7: warning: variable 'it1' set but not used [-Wunused-but-set-variable]
   96 |  auto it1 = it, it2 = it;
      |       ^~~

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