Submission #300407

#	Time	Username	Problem	Language	Result	Execution time	Memory
300407		kshitij_sodani	Comparing Plants (IOI20_plants)	C++14	14 / 100	4038 ms	14584 KiB

plants

#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back

typedef long long llo;
#include "plants.h"
vector<int> it;
int n;

int k;
pair<int,int> tree[800001];
int lazy[800001];
void build(int no,int l,int r){
	if(l==r){
		tree[no]={it[l],l};
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		if(tree[no*2+1].a<tree[no*2+2].a){
			tree[no]=tree[no*2+1];
		}
		else{
			tree[no]=tree[no*2+2];
		}
	}
}
void update(int no,int l,int r,int aa,int bb){
	tree[no].a+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;
	if(l>aa or r<bb){
		return ;
	}
	if(aa<=l and r<=bb){
		tree[no].a-=1;
		if(l<r){
			lazy[no*2+1]-=1;
			lazy[no*2+2]-=1;
		}
	}
	else{
		int mid=(l+r)/2;
		update(no*2+1,l,mid,aa,bb);
		update(no*2+2,mid+1,r,aa,bb);
		if(tree[no*2+1].a<tree[no*2+2].a){
			tree[no]=tree[no*2+1];
		}
		else{
			tree[no]=tree[no*2+2];
		}
	}
}
void update2(int no,int l,int r,int i){
	tree[no].a+=lazy[no];
	if(l<r){
		lazy[no*2+1]+=lazy[no];
		lazy[no*2+2]+=lazy[no];
	}
	lazy[no]=0;
	if(l==r){
		tree[no]={1e9,-1};
	}
	else{
		int mid=(l+r)/2;
		if(i<=mid){
			update2(no*2+1,l,mid,i);
		}
		else{
			update2(no*2+2,mid+1,r,i);
		}
		if(tree[no*2+1].a<tree[no*2+2].a){
			tree[no]=tree[no*2+1];
		}
		else{
			tree[no]=tree[no*2+2];
		}
	}
}

int tree2[200001];
void u(int i,int j){
	while(i<200001){
		tree2[i]+=j;
		i+=(i&-i);
	}
}
int ss(int i){
	int su=0;
	while(i>0){
		su+=tree2[i];
		i-=(i&-i);
	}
	return su;
}
int ans[200001];
set<int> cur;

bool check(int j){
	if(cur.size()==1){
		return true;
	}
	auto jj=cur.find(j);
	int dis;
	if(jj==cur.begin()){
		jj=cur.end();
		jj--;
		dis=j+n-*jj;
	}
	else{
		jj--;
		dis=j-*jj;
	}
	if(dis>k-1){
		return true;
	}
	return false;

}
void init(int kk,vector<int> r){
	n=r.size();
	k=kk;
	it=r;
	
	build(0,0,n-1);
	set<int> cur2;
	for(int i=0;i<n;i++){
		if(it[i]==0){
			cur.insert(i);
			update2(0,0,n-1,i);
		}
	}
	for(auto j:cur){
		if(check(j)){
			cur2.insert(j);
		}
	}
	for(int i=0;i<n;i++){
		int ind=-1;
		cur2.clear();
		for(auto j:cur){
			if(check(j)){
				cur2.insert(j);
			}
		}

		ind=*(cur2.begin());
		ans[ind]=i;


		//int cot=ind;
		cur2.erase(ind);
		cur.erase(ind);
		if(cur.size()){
			auto j=cur.upper_bound(ind);
			if(j!=cur.end()){
				if(check(*j)){
					cur2.insert(*j);
				}
			}
			else{
				j=cur.begin();
				if(check(*j)){
					cur2.insert(*j);
				}
			}
		}
		//cout<<ind<<endl;
		
		if(ind>=k-1){
			update(0,0,n-1,ind-k+1,ind-1);
		}
		else{
			if(ind){
				update(0,0,n-1,0,ind-1);
			}
			int xx=(ind-k+1+n)%n;
			update(0,0,n-1,xx,n-1);
		}
		int cot=ind;
		for(int jj=0;jj<k-1;jj++){
			cot=(cot-1+n)%n;
			it[cot]-=1;
			if(it[cot]==0){
				cur.insert(cot);
				if(cur.size()>1){
					auto j=cur.upper_bound(cot);
					if(j==cur.end()){
						j=cur.begin();
						cur2.erase(*j);
						if(check(*j)){
							cur2.insert(*j);
						}
					}
					else{
						cur2.erase(*j);
						if(check(*j)){
							cur2.insert(*j);
						}	
					}
				}
				//cout<<tree[0].b<<endl;
				//cur.insert(cot);
				if(check(cot)){
					cur2.insert(tree[0].b);
				}
				//update2(0,0,n-1,tree[0].b);
			}
		}
		continue;
		
		/*if(tree[0].a<0){
			while(true){
				continue;
			}
		}*/
		while(tree[0].a==0){
			cur.insert(tree[0].b);

			if(cur.size()>1){
				auto j=cur.upper_bound(tree[0].b);
				if(j==cur.end()){
					j=cur.begin();
					cur2.erase(*j);
					if(check(*j)){
						cur2.insert(*j);
					}
				}
				else{
					cur2.erase(*j);
					if(check(*j)){
						cur2.insert(*j);
					}	
				}
			}
			//cout<<tree[0].b<<endl;
			
			if(check(tree[0].b)){
				cur2.insert(tree[0].b);
			}
			update2(0,0,n-1,tree[0].b);
		}

	}




	return;
}

int compare_plants(int x, int y) {
/*	x=dis[x];
	y=dis[y];*/
	if(ans[x]<ans[y]){
		return 1;
	}
	else{
		return -1;
	}
	return 0;


	if(y-x<k){
		if(it[x]==0){
			return 1;
		}
		else if(it[x]==k-1){
			return -1;
		}
	}
	else{
		if(it[y]==0){
			return -1;
		}
		else if(it[y]==k-1){
			return 1;
		}
	}


	return 0;
}

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