Submission #306053

#	Time	Username	Problem	Language	Result	Execution time	Memory
306053		gs18115	Comparing Plants (IOI20_plants)	C++14	0 / 100	123 ms	16376 KiB

plants

#include"plants.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=200010;
struct seg
{
	pi t[mx*4];
	int lz[mx*4];
	void init(int n,int s,int e,vector<int>&v)
	{
		lz[n]=0;
		if(s==e)
		{
			t[n]=pi(v[s],s);
			return;
		}
		int m=s+(e-s)/2;
		init(n*2,s,m,v);
		init(n*2+1,m+1,e,v);
		t[n]=min(t[n*2],t[n*2+1]);
		return;
	}
	inline void put(int n,int p)
	{
		t[n].fi+=p;
		lz[n]+=p;
		return;
	}
	inline void prop(int n)
	{
		if(lz[n]==0)
			return;
		put(n*2,lz[n]);
		put(n*2+1,lz[n]);
		lz[n]=0;
		return;
	}
	void upd(int n,int s,int e,int S,int E,int p)
	{
		if(s>E||S>e)
			return;
		if(S<=s&&e<=E)
			return put(n,p);
		prop(n);
		int m=s+(e-s)/2;
		upd(n*2,s,m,S,E,p);
		upd(n*2+1,m+1,e,S,E,p);
		t[n]=min(t[n*2],t[n*2+1]);
		return;
	}
}st1,st2;
struct seg2
{
	int t[mx*4];
	void init(int n,int s,int e,int v)
	{
		t[n]=v;
		if(s==e)
			return;
		int m=s+(e-s)/2;
		init(n*2,s,m,v);
		init(n*2+1,m+1,e,v);
		return;
	}
	void put(int n,int s,int e,int x,int p)
	{
		if(s==e)
		{
			t[n]=p;
			return;
		}
		int m=s+(e-s)/2;
		if(x>m)
			put(n*2+1,m+1,e,x,p);
		else
			put(n*2,s,m,x,p);
		t[n]=min(t[n*2],t[n*2+1]);
		return;
	}
	int query(int n,int s,int e,int S,int E)
	{
		if(s>E||S>e)
			return inf;
		if(S<=s&&e<=E)
			return t[n];
		int m=s+(e-s)/2;
		return min(query(n*2,s,m,S,E),query(n*2+1,m+1,e,S,E));
	}
}st3;
int ord[mx];
vector<int>ov;
int spa1[mx][20],spd1[mx][20];
int spa2[mx][20],spd2[mx][20];
int n;
void init(int k,vector<int>r)
{
	n=r.size();
	st1.init(1,0,n-1,r);
	st2.init(1,0,n-1,r);
	for(int i=0;i<n;i++)
	{
		while(st2.t[1].fi==0)
		{
			int cur=st2.t[1].se;
			st2.upd(1,0,n-1,cur,cur,inf);
			st1.upd(1,0,n-1,cur+1,cur+k-1,1),st1.upd(1,0,n-1,0,cur+k-1-n,1);
		}
		int cur=st1.t[1].se;
		ord[cur]=i;
		ov.eb(cur);
		st1.upd(1,0,n-1,cur,cur,inf);
		st1.upd(1,0,n-1,cur-k+1+n,n-1,-1),st1.upd(1,0,n-1,cur-k+1,cur-1,-1);
		st1.upd(1,0,n-1,cur+1,cur+k-1,-1),st1.upd(1,0,n-1,0,cur+k-1-n,-1);
		st2.upd(1,0,n-1,cur-k+1+n,n-1,-1),st2.upd(1,0,n-1,cur-k+1,cur-1,-1);
	}
	st3.init(1,0,n-1,n);
	auto get3=[&](const int&p)->int{return min(st3.query(1,0,n-1,p-k+1,p-1),
	st3.query(1,0,n-1,p-k+1+n,n-1));};
	auto get4=[&](const int&p)->int{return min(st3.query(1,0,n-1,p+1,p+k-1),
	st3.query(1,0,n-1,0,p+k-1-n));};
	ov.eb(ord[n]=n);
	for(int i=0;i<20;i++)
		spa1[n][i]=spa2[n][i]=n,spd1[n][i]=spd2[n][i]=0;
	for(int i=n;i-->0;)
	{
		int cur=ov[i];
		int nx=ov[get3(cur)];
		spa1[cur][0]=nx,spd1[cur][0]=nx>cur?1:0;
		nx=ov[get4(cur)];
		spa2[cur][0]=nx,spd2[cur][0]=nx<cur?1:0;
		st3.put(1,0,n-1,cur,i);
	}
	for(int j=0;j<19;j++)
		for(int i=0;i<=n;i++)
			spa1[i][j+1]=spa1[spa1[i][j]][j],
			spd1[i][j+1]=spd1[spa1[i][j]][j]+spd1[i][j],
			spa2[i][j+1]=spa1[spa2[i][j]][j],
			spd2[i][j+1]=spd1[spa2[i][j]][j]+spd2[i][j];
	return;
}
int compare_plants(int x,int y)
{
	int p=1;
	if(ord[x]>ord[y])
		swap(x,y),p=-1;
	int l=x,ld=0;
	int r=x,rd=0;
	for(int i=20;i-->0;)
		if(ord[spa1[l][i]]<=ord[y])
			ld+=spd1[l][i],l=spa1[l][i];
	for(int i=20;i-->0;)
		if(ord[spa2[r][i]]<=ord[y])
			rd+=spd2[r][i],r=spa2[r][i];
	l-=n*min(2,ld),r+=n*min(2,rd);
	for(int i=-1;i<=1;i++)
		if(l+i*n<=y&&y<=r+i*n)
			return p;
	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