Submission #424116

#	Time	Username	Problem	Language	Result	Execution time	Memory
424116		mosiashvililuka	Comparing Plants (IOI20_plants)	C++14	100 / 100	1702 ms	61116 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,e,i,j,ii,jj,zx,xc,k,R[200009],cnt,f[200009],seg[800009],seg2[800009],segmn[800009],za,l,r,z,zz,ll,rr,RE[200009];
int rg[200009][20],lf[200009][20];
set <int> s;
set <int>::iterator it,tt;
set <pair <int, int> > st;
set <pair <int, int> >::iterator IT;
void pushdown(int q, int w, int rr){
	if(q!=w){
		seg2[rr*2]+=seg2[rr];
		seg2[rr*2+1]+=seg2[rr];
	}
	segmn[rr]+=seg2[rr];
	seg2[rr]=0;
}
void upd(int q, int w, int rr){
	pushdown(q,w,rr);
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		seg2[rr]+=z;
		pushdown(q,w,rr);
		return;
	}
	upd(q,(q+w)/2,rr*2);
	upd((q+w)/2+1,w,rr*2+1);
	if(segmn[rr*2]<segmn[rr*2+1]){
		seg[rr]=seg[rr*2];segmn[rr]=segmn[rr*2];
	}
	if(segmn[rr*2]>segmn[rr*2+1]){
		seg[rr]=seg[rr*2+1];segmn[rr]=segmn[rr*2+1];
	}
	if(segmn[rr*2]==segmn[rr*2+1]){
		segmn[rr]=segmn[rr*2+1];
		seg[rr]=min(seg[rr*2],seg[rr*2+1]);
	}
}
void UPD(int q, int w, int rr){
	l=q+1;r=w+1;z=rr;
	upd(1,za,1);
}
void read(int q, int w, int rr){
	pushdown(q,w,rr);
	if(q>r||w<l) return;
	if(q>=l&&w<=r){
		if(z>segmn[rr]){
			z=segmn[rr];zz=seg[rr];
		}else{
			if(z==segmn[rr]){
				if(zz>seg[rr]) zz=seg[rr];
			}
		}
		return;
	}
	read(q,(q+w)/2,rr*2);
	read((q+w)/2+1,w,rr*2+1);
}
void READ(int q, int w){
	q++;w++;
	while(q<=w){
		l=q;r=w;z=a+3;zz=a+3;
		read(1,za,1);
		if(z!=0||zz>w) break;
		zz--;
		it=s.lower_bound(zz);
		if(it==s.end()) it=s.begin();
		if(it!=s.begin()){
			tt=it;tt--;
		}else{
			tt=s.end();tt--;
		}
		st.erase(st.lower_bound(make_pair(((*it)+a-(*tt))%a,(*it))));
		st.insert(make_pair(((*it)+a-zz)%a,(*it)));
		st.insert(make_pair((zz+a-(*tt))%a,zz));
		s.insert(zz);
		zz++;
		q=zz+1;
	}
}
void init(int Kk, vector<int> Rr) {
	a=Rr.size();k=Kk-1;
	for(i=0; i<a; i++){
		R[i]=Rr[i];
	}
	za=1;
	while(za<a) za*=2;
	for(i=0; i<a; i++){
		seg[za+i]=i+1;segmn[za+i]=R[i];
		if(R[i]==0){
			s.insert(i);
		}
	}
	for(i=za-1; i>=1; i--){
		if(segmn[i*2]<segmn[i*2+1]){
			seg[i]=seg[i*2];segmn[i]=segmn[i*2];
		}
		if(segmn[i*2]>segmn[i*2+1]){
			seg[i]=seg[i*2+1];segmn[i]=segmn[i*2+1];
		}
		if(segmn[i*2]==segmn[i*2+1]){
			segmn[i]=segmn[i*2+1];
			seg[i]=min(seg[i*2],seg[i*2+1]);
		}
	}
	for(it=s.begin(); it!=s.end(); it++){
		tt=it;tt++;
		if(tt==s.end()) tt=s.begin();
		st.insert(make_pair(((*tt)+a-(*it))%a,(*tt)));
	}
	cnt=a;
	while(cnt>0){
		IT=st.end();IT--;
		i=(*IT).second;
		f[i]=cnt;cnt--;
		if(cnt==0) break;
		if(i-k>=0){
			UPD(i-k,i-1,-1);
			READ(i-k,i-1);
		}else{
			UPD(0,i-1,-1);
			UPD(a-(k-i),a-1,-1);
			READ(0,i-1);
			READ(a-(k-i),a-1);
		}
		s.erase(s.lower_bound(i));
		it=s.lower_bound(i);
		if(it==s.end()) it=s.begin();
		if(it!=s.begin()){
			tt=it;tt--;
		}else{
			tt=s.end();tt--;
		}
		st.erase(st.lower_bound(make_pair(((*it)+a-i)%a,(*it))));
		st.erase(st.lower_bound(make_pair((i+a-(*tt))%a,i)));
		st.insert(make_pair(((*it)+a-(*tt))%a,(*it)));
		l=i+1;r=i+1;z=a+3;
		upd(1,za,1);
	}
	st.clear();
	for(j=0; j<k; j++){
		st.insert(make_pair(f[j],j));
	}
	for(i=0; i<a; i++){
		st.erase(st.lower_bound(make_pair(f[i],i)));
		st.insert(make_pair(f[(i+k)%a],(i+k)%a));
		IT=st.lower_bound(make_pair(f[i],0));
		if(IT==st.begin()){
			rg[i][0]=-1;
		}else{
			IT--;
			rg[i][0]=(*IT).second;
		}
	}
	st.clear();
	for(j=a-1; j>=a-k; j--){
		st.insert(make_pair(f[j],j));
	}
	for(i=a-1; i>=0; i--){
		st.erase(st.lower_bound(make_pair(f[i],i)));
		st.insert(make_pair(f[(i+a-k)%a],(i+a-k)%a));
		IT=st.lower_bound(make_pair(f[i],0));
		if(IT==st.begin()){
			lf[i][0]=-1;
		}else{
			IT--;
			lf[i][0]=(*IT).second;
		}
	}
	for(j=1; j<=18; j++){
		for(i=0; i<a; i++){
			if(rg[i][j-1]==-1){
				rg[i][j]=-1;
				continue;
			}
			zx=rg[rg[i][j-1]][j-1];
			if(zx==-1){
				rg[i][j]=-1;
				continue;
			}
			if(i<=zx){
				l=i;r=zx;
				ll=l;rr=r;
			}else{
				l=i;r=a-1;
				ll=0;rr=zx;
			}
			if((l<=rg[i][j-1]&&rg[i][j-1]<=r)||(ll<=rg[i][j-1]&&rg[i][j-1]<=rr)){
				rg[i][j]=zx;
			}else{
				rg[i][j]=-1;
				continue;
			}
		}
	}
	for(j=1; j<=18; j++){
		for(i=0; i<a; i++){
			if(lf[i][j-1]==-1){
				lf[i][j]=-1;
				continue;
			}
			zx=lf[lf[i][j-1]][j-1];
			if(zx==-1){
				lf[i][j]=-1;
				continue;
			}
			if(i>=zx){
				l=zx;r=i;
				ll=l;rr=r;
			}else{
				l=zx;r=a-1;
				ll=0;rr=i;
			}
			if((l<=lf[i][j-1]&&lf[i][j-1]<=r)||(ll<=lf[i][j-1]&&lf[i][j-1]<=rr)){
				lf[i][j]=zx;
			}else{
				lf[i][j]=-1;
				continue;
			}
		}
	}
	return;
}
int compare_plants(int x, int y) {
	c=x;d=y;
	for(j=18; j>=0; j--){
		if(c<=d){
			l=c;r=d;
			ll=l;rr=r;
		}else{
			l=c;r=a-1;
			ll=0;rr=d;
		}
		if(rg[c][j]==-1) continue;
		if((l<=rg[c][j]&&rg[c][j]<=r)||(ll<=rg[c][j]&&rg[c][j]<=rr)){
			c=rg[c][j];
		}
	}
	if((d+a-c)%a<=k&&f[c]>=f[d]){
		return 1;
	}
	c=x;d=y;
	for(j=18; j>=0; j--){
		if(c>=d){
			l=d;r=c;
			ll=l;rr=r;
		}else{
			l=d;r=a-1;
			ll=0;rr=c;
		}
		if(lf[c][j]==-1) continue;
		if((l<=lf[c][j]&&lf[c][j]<=r)||(ll<=lf[c][j]&&lf[c][j]<=rr)){
			c=lf[c][j];
		}
	}
	if((c+a-d)%a<=k&&f[c]>=f[d]){
		return 1;
	}
	c=y;d=x;
	for(j=18; j>=0; j--){
		if(c<=d){
			l=c;r=d;
			ll=l;rr=r;
		}else{
			l=c;r=a-1;
			ll=0;rr=d;
		}
		if(rg[c][j]==-1) continue;
		if((l<=rg[c][j]&&rg[c][j]<=r)||(ll<=rg[c][j]&&rg[c][j]<=rr)){
			c=rg[c][j];
		}
	}
	if((d+a-c)%a<=k&&f[c]>=f[d]){
		return -1;
	}
	c=y;d=x;
	for(j=18; j>=0; j--){
		if(c>=d){
			l=d;r=c;
			ll=l;rr=r;
		}else{
			l=d;r=a-1;
			ll=0;rr=c;
		}
		if(lf[c][j]==-1) continue;
		if((l<=lf[c][j]&&lf[c][j]<=r)||(ll<=lf[c][j]&&lf[c][j]<=rr)){
			c=lf[c][j];
		}
	}
	if((c+a-d)%a<=k&&f[c]>=f[d]){
		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