제출 #528805

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528805		jamezzz	Comparing Plants (IOI20_plants)	C++17	0 / 100	20 ms	31768 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;

struct node2{
	int s,e,m,mn,mx;
	node2 *l,*r;
	node2(int _s,int _e){
		s=_s;e=_e;m=(s+e)/2;mn=maxn;mx=-maxn;
		if(s!=e)l=new node2(s,m),r=new node2(m+1,e);
	}
	void up(int x,int nv){
		if(s==x&&e==x){mn=mx=nv;return;}
		if(x<=m)l->up(x,nv);
		else r->up(x,nv);
		mn=min(l->mn,r->mn);
		mx=max(l->mx,r->mx);
	}
	int qmn(int x,int y){
		if(s==x&&e==y)return mn;
		if(y<=m)return l->qmn(x,y);
		if(x>m)return r->qmn(x,y);
		return min(l->qmn(x,m),r->qmn(m+1,y));
	}
	int qmx(int x,int y){
		if(s==x&&e==y)return mx;
		if(y<=m)return l->qmx(x,y);
		if(x>m)return r->qmx(x,y);
		return max(l->qmx(x,m),r->qmx(m+1,y));
	}
	int qmn2(int x,int y){
		if(x<=y)return qmn(x,y);
		else{
			int t=qmn(x,n-1);
			if(t!=maxn)return t;
			else return qmn(0,y);
		}
	}
	int qmx2(int x,int y){
		if(x<=y)return qmx(x,y);
		else{
			int t=qmx(0,y);
			if(t!=-maxn)return t;
			else return qmx(x,n-1);
		}
	}
}*root2;

int maxb,h[maxn],nx[maxn][20],pv[maxn][20];
bool done[maxn];
vector<int> z;
stack<int> st;
deque<ii> dq;

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]);
		if(r[i]==0){
			z.pb(i);
		}
	}
	while(!z.empty()){
		int cur=z.back();z.pop_back();
		if(done[cur])continue;
		while(true){
			ii res=(root->qry2(sub(cur,k-1),sub(cur,1)));
			st.push(cur);done[cur]=true;
			if(res.fi==0)cur=res.se;
			else break;
		}
		while(!st.empty()){
			cur=st.top();st.pop();
			int a=sub(cur,k-1),b=sub(cur,1);
			ii res=root->qry2(a,b);
			if(res.fi==0){
				st.push(cur);
				break;
			}
			h[cur]=cnt--;
			root->up2(a,b,-1);
			root->up(cur,cur,maxn);
			while(true){
				ii res=root->qry2(a,b);
				if(res.fi==0){
					z.pb(res.se);
					root->up(res.se,res.se,maxn);
				}
				else break;
			}
		}
	}
	memset(pv,-1,sizeof pv);
	memset(nx,-1,sizeof nx);
	root2=new node2(0,n-1);
	vector<ii> srt;
	for(int i=0;i<n;++i)srt.pb({h[i],i});
	sort(srt.begin(),srt.end(),greater<ii>());
	for(ii pr:srt){
		int i=pr.se;
		int t=root2->qmn2(sub(i,k-1),sub(i,1));
		if(t!=maxn)pv[i][0]=t;
		t=root2->qmx2(add(i,1),add(i,k-1));
		if(t!=-maxn)nx[i][0]=t;
		root2->up(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)nx[i][j]=nx[nx[i][j-1]][j-1];
			if(pv[i][j-1]!=-1)pv[i][j]=pv[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(t!=y&&sub(y,t)+sub(t,x)==sub(y,x))x=t;
	}
	if(h[x]<h[y]&&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(t!=y&&sub(x,t)+sub(t,y)==sub(x,y))x=t;
	}
	if(h[x]<h[y]&&sub(x,y)<=k)return true;
	return false;
}

int compare_plants(int x,int y){
	bool a=check(x,y),b=check(y,x);
	if(a==b)return 0;
	if(a==1)return -1;
	else return 1;
}

• 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