Submission #529646

#	Time	Username	Problem	Language	Result	Execution time	Memory
529646		jamezzz	Comparing Plants (IOI20_plants)	C++17	100 / 100	1177 ms	95716 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define pf printf
#define pb push_back
typedef pair<int,int> ii;

#define maxn 200005

int n,k;

inline int add(int a,int b){return (a+b)%n;}
inline int sub(int a,int b){return (a-b+n)%n;}

struct node{
	int s,e,m,lz;ii v;
	node *l,*r;
	node(int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;lz=0;v={0,s};
		if(s!=e)l=new node(s,m),r=new node(m+1,e);
	}
	void ppo(){
		v.fi+=lz;
		if(lz!=0&&s!=e)l->lz+=lz,r->lz+=lz;
		lz=0;
	}
	void up(int x,int y,int nv){
		if(s==x&&e==y){lz+=nv;return;}
		if(y<=m)l->up(x,y,nv);
		else if(x>m)r->up(x,y,nv);
		else l->up(x,m,nv),r->up(m+1,y,nv);
		l->ppo();r->ppo();v=min(l->v,r->v);
	}
	ii qry(int x,int y){
		ppo();
		if(s==x&&e==y)return v;
		if(y<=m)return l->qry(x,y);
		if(x>m)return r->qry(x,y);
		return min(l->qry(x,m),r->qry(m+1,y));
	}
	void up2(int x,int y,int nv){
		if(x<=y)up(x,y,nv);
		else up(0,y,nv),up(x,n-1,nv);
	}
	ii qry2(int x,int y){
		if(x<=y)return qry(x,y);
		else return min(qry(0,y),qry(x,n-1));
	}
}*root;

int maxb,h[maxn],nx[maxn][20],pv[maxn][20],dnx[maxn][20],dpv[maxn][20];
stack<int> st;
set<ii> s;

void init(int _k,vector<int> r){
	n=r.size();k=_k;
	root=new node(0,n-1);
	int cnt=n-1;
	for(int i=0;i<n;++i){
		root->up(i,i,r[i]);
	}
	while(cnt>=0){
		if(st.empty()){
			st.push((root->qry(0,n-1)).se);
		}
		int cur=st.top();
		ii pr=root->qry2(sub(cur,k-1),sub(cur,1));
		if(pr.fi==0){
			st.push(pr.se);continue;
		}
		h[cur]=cnt--;
		root->up(cur,cur,maxn);
		root->up2(sub(cur,k-1),sub(cur,1),-1);
		st.pop();
	}
	memset(pv,-1,sizeof pv);
	memset(nx,-1,sizeof nx);
	for(int i=0;i<k-1;++i)s.insert({h[i],i});
	for(int i=n-1;i>=0;--i){
		auto it=s.upper_bound({h[i],0});
		if(it!=s.end()){
			nx[i][0]=(*it).se;
			dnx[i][0]=sub(nx[i][0],i);
		}
		s.erase(s.find({h[add(i,k-1)],add(i,k-1)}));
		s.insert({h[i],i});
	}
	s.clear();
	for(int i=sub(n,k-1);i<n;++i)s.insert({h[i],i});
	for(int i=0;i<n;++i){
		auto it=s.upper_bound({h[i],0});
		if(it!=s.end()){
			pv[i][0]=(*it).se;
			dpv[i][0]=sub(i,pv[i][0]);
		}
		s.erase(s.find({h[sub(i,k-1)],sub(i,k-1)}));
		s.insert({h[i],i});
	}
	for(int j=1;(1<<j)<=n;++j){
		maxb=j;
		for(int i=0;i<n;++i){
			if(nx[i][j-1]!=-1&&dnx[i][j-1]+dnx[nx[i][j-1]][j-1]<=n){
				nx[i][j]=nx[nx[i][j-1]][j-1];
				dnx[i][j]=dnx[i][j-1]+dnx[nx[i][j-1]][j-1];
			}
			if(pv[i][j-1]!=-1&&dpv[i][j-1]+dpv[pv[i][j-1]][j-1]<=n){
				pv[i][j]=pv[pv[i][j-1]][j-1];
				dpv[i][j]=dpv[i][j-1]+dpv[pv[i][j-1]][j-1];
			}
		}
	}
}

bool check(int x,int y){//is x<y
	int tmp=x;
	for(int i=maxb;i>=0;--i){
		int t=nx[x][i];
		if(t==-1)continue;
		if(sub(y,t)+sub(t,x)==sub(y,x)&&h[t]<=h[y])x=t;
	}
	if(sub(y,x)<k)return true;
	x=tmp;
	for(int i=maxb;i>=0;--i){
		int t=pv[x][i];
		if(t==-1)continue;
		if(sub(x,t)+sub(t,y)==sub(x,y)&&h[t]<=h[y])x=t;
	}
	if(sub(x,y)<k)return true;
	return false;
}

int compare_plants(int x,int y){
	int ans=-1;
	if(h[x]>h[y])ans=1,swap(x,y);
	if(!check(x,y))ans=0;
	return ans;
}

• 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