Submission #1039876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039876		amirhoseinfar1385	Comparing Plants (IOI20_plants)	C++17	0 / 100	33 ms	36056 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=200000+10,lg=19,kaf=(1<<lg);
long long all[maxn],tr[maxn],fake[maxn],allh[maxn];
long long k,n,vis[maxn],visa[maxn];
vector<long long>adj[maxn];
long long inf=1e15;

struct segment{
	long long lazy[(1<<(lg+1))];
	pair<long long,long long>seg[(1<<(lg+1))];
	segment(){
		for(long long i=(1<<(lg+1));i>=1;i--){
			if(i>=kaf){
				seg[i]=make_pair(0,i-kaf);
			}else{
				seg[i]=min(seg[(i<<1)],seg[(i<<1)^1]);
			}
		}
	}
	void calc(long long i){
		if(i>=kaf){
			seg[i].first+=lazy[i];
			lazy[i]=0;
			return ;
		}
		seg[i]=min(make_pair(seg[(i<<1)].first+lazy[(i<<1)],seg[(i<<1)].second),make_pair(seg[(i<<1)^1].first+lazy[(i<<1)^1],seg[(i<<1)^1].second));
	}
	void shift(long long i){
		if(i>=kaf){
			return ;
		}
		lazy[(i<<1)]+=lazy[i];
		lazy[(i<<1)^1]+=lazy[i];
		lazy[i]=0;
	}
	void upd(long long i,long long l,long long r,long long tl,long long tr,long long w){
		if(l>r||l>tr||r<tl||tl>tr){
			return ;
		}
		if(l>=tl&&r<=tr){
			lazy[i]+=w;
			shift(i);
			calc(i);
			return ;
		}
		shift(i);
		long long m=(l+r)>>1;
		upd((i<<1),l,m,tl,tr,w);
		upd((i<<1)^1,m+1,r,tl,tr,w);
		calc(i);
		return ;
	}
	pair<long long ,long long> pors(long long i,long long l,long long r,long long tl,long long tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return make_pair(inf,inf);
		}
		shift(i);
		calc(i);
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		long long m=(l+r)>>1;
		return min(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
	}
}seg;

void init(int k_, std::vector<int> r) {
	k=k_;
	n=(long long)r.size();
	for(long long i=0;i<n;i++){
		all[i]=r[i];
	}
	for(long long i=0;i<n;i++){
		fake[i]=all[i];
		seg.upd(1,0,kaf-1,i,i,all[i]);
	}
	long long cnt=n;
	for(long long i=0;i<n;i++){
		vector<long long>tofy;
		tofy.push_back(seg.pors(1,0,kaf-1,0,n-1).second);
		//cout<<seg.pors(1,0,kaf-1,0,n-1).first<<" "<<seg.pors(1,0,kaf-1,0,n-1).second<<endl;
		//for(long long h=1;h<=k-1;h++){
	//		fake[(tofy.back()-h+n)%n]--;
	//		if(vis[(tofy.back()-h+n)%n]==0){
	//			adj[tofy.back()].push_back((tofy.back()-h+n)%n);
	//		}
	//	}
		if(tofy.back()>=k-1){
			seg.upd(1,0,kaf-1,tofy.back()-k+1,tofy.back()-1,-1);
		}else{
			seg.upd(1,0,kaf-1,0,tofy.back()-1,-1);
			long long l=(tofy.back()-(k-1)+n)%n;
			seg.upd(1,0,kaf-1,l,n-1,-1);
		//	cout<<l<<endl;
		}
		seg.upd(1,0,kaf-1,tofy.back(),tofy.back(),inf);
		vis[tofy.back()]=1;
		fake[tofy.back()]=-1;
		allh[tofy.back()]=cnt;
		cnt--;
	}
}

int compare_plants(int x,int y) {
	if(allh[x]>allh[y]){
		return 1;
	}
	if(allh[y]>allh[x]){
		return -1;
	}
	return 0;
}

• 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