Submission #1276769

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276769		boclobanchat	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	100 / 100	862 ms	19444 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN=6e5+5;
const int INF=1e9;
int A[MAXN],B[MAXN],C[MAXN],L[MAXN],R[MAXN],st[MAXN];
int pf[MAXN],ps[MAXN],p[MAXN],pref[MAXN];
int qf[MAXN],qs[MAXN],q[MAXN],qref[MAXN];
int getinput()
{
    int ans=0;
    char c=getchar();
    while(c==' '||c=='\n') c=getchar();
    while(c>='0'&&c<='9') ans=ans*10+c-'0',c=getchar();
    return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n=getinput();
	for(int i=0;i<n*2;i++) A[i]=getinput();
	for(int i=1;i<=n;i++) B[i]=getinput();
	for(int i=1;i<=n;i++) C[i]=getinput();
	sort(B+1,B+n+1);
	sort(C+1,C+n+1);
	int pt,lt,rt,pl,pr,ql,qr;
	B[0]=C[0]=-INF*2-7,B[n+1]=C[n+1]=INF*2+7;
	for(int i=0;i<n;i++) p[i]=q[i]=0,p[i+n]=q[i+n]=n+1;
	L[1]=R[1]=n,pf[1]=abs(B[n]-A[n]),qf[1]=abs(C[n]-A[n]);
	for(int i=2;i<=n;i++)
	{
		L[i]=L[i-1],R[i]=R[i-1];
		if(A[L[i]-1]>A[R[i]+1])
		{
			L[i]--;
			pf[i]=max(pf[i-1],abs(B[n-i+1]-A[L[i]]));
			qf[i]=max(qf[i-1],abs(C[n-i+1]-A[L[i]]));
		}
		else
		{
			R[i]++;
			pf[i]=max(pf[i-1],abs(B[n-i+1]-A[R[i]]));
			qf[i]=max(qf[i-1],abs(C[n-i+1]-A[R[i]]));
		}
	}
	pt=1;
	for(int i=1;;i++)
	{
		while(i<=L[pt]&&R[pt]<=i+n-1) pt++;
		pt--,ps[i]=pf[pt],qs[i]=qf[pt];
		if(i==1) pl=rt=L[pt]-1;
		else
		{
			p[i-1]=i-1;
			while(rt>=L[pt]) p[rt--]=i-1;
		}
		if(pt==n) break;
		pt++;
	}
	pt=1;
	for(int i=n;;i--)
	{
		while(i<=L[pt]&&R[pt]<=i+n-1) pt++;
		pt--,ps[i]=pf[pt],qs[i]=qf[pt];
		if(i==n) pr=lt=R[pt]+1;
		else
		{
			while(lt<=R[pt]) p[lt++]=i+1;
			p[i+n]=i+1;
		}
		if(pt==n) break;
		pt++;
	}
	L[1]=R[1]=n,pf[1]=abs(C[1]-A[0]),qf[1]=abs(B[1]-A[0]);
	for(int i=2;i<=n;i++)
	{
		L[i]=L[i-1],R[i]=R[i-1];
		if(A[L[i]-1+n]<A[R[i]+1-n])
		{
			L[i]--;
			pf[i]=max(pf[i-1],abs(C[i]-A[L[i]+n]));
			qf[i]=max(qf[i-1],abs(B[i]-A[L[i]+n]));
		}
		else
		{
			R[i]++;
			pf[i]=max(pf[i-1],abs(C[i]-A[R[i]-n]));
			qf[i]=max(qf[i-1],abs(B[i]-A[R[i]-n]));
		}
	}
	pt=1;
	for(int i=1;;i++)
	{
		while(i<=L[pt]&&R[pt]<=i+n-1) pt++;
		pt--,ps[i]=max(ps[i],pf[pt]),qs[i]=max(qs[i],qf[pt]);
		if(i==1) ql=rt=L[pt]-1;
		else
		{
			q[i-1]=i-1;
			while(rt>=L[pt]) q[rt--]=i-1;
		}
		if(pt==n) break;
		pt++;
	}
	pt=1;
	for(int i=n;;i--)
	{
		while(i<=L[pt]&&R[pt]<=i+n-1) pt++;
		pt--,ps[i]=max(ps[i],pf[pt]),qs[i]=max(qs[i],qf[pt]);
		if(i==n) qr=lt=R[pt]+1;
		else
		{
			while(lt<=R[pt]) q[lt++]=i+1;
			q[i+n]=i+1;
		}
		if(pt==n) break;
		pt++;
	}
	for(int i=1;i<=pl;i++) st[1]++,st[p[i]+1]--;
	for(int i=n*2-1;i>=pr;i--) st[p[i]]++;
	for(int i=1;i<=ql;i++) st[1]++,st[q[i]+1]--;
	for(int i=n*2-1;i>=qr;i--) st[q[i]]++;
	int l=0,r=INF,ans=INF,ll,rr;
	while(l<=r)
	{
		int mid=(l+r)/2;
		for(int i=0;i<=n+1;i++) pref[i]=st[i];
		lt=rt=1;
		for(int i=1;i<=pl;i++)
		{
			while(B[lt]<A[i]-mid) lt++;
			while(B[rt]<=A[i]+mid) rt++;
			ll=max(i-rt+2,1),rr=min(i-lt+1,p[i]);
			if(ll<=rr) pref[ll]--,pref[rr+1]++;
		}
		lt=rt=1;
		for(int i=n*2-1;i>=pr;i--)
		{
			while(B[lt]<A[i]-mid) lt++;
			while(B[rt]<=A[i]+mid) rt++;
			ll=max(i-n+lt,p[i]),rr=min(i-n+rt-1,n);
			if(ll<=rr) pref[ll]--,pref[rr+1]++;
		}
		lt=rt=n;
		for(int i=1;i<=ql;i++)
		{
			while(C[rt]>A[i+n]+mid) rt--;
			while(C[lt]>=A[i+n]-mid) lt--;
			ll=max(i-n+lt+1,1),rr=min(i-n+rt,q[i]);
			if(ll<=rr) pref[ll]--,pref[rr+1]++;
		}
		lt=rt=n;
		for(int i=n*2-1;i>=qr;i--)
		{
			while(C[rt]>A[i-n]+mid) rt--;
			while(C[lt]>=A[i-n]-mid) lt--;
			ll=max(i-rt+1,q[i]),rr=min(i-lt,n);
			if(ll<=rr) pref[ll]--,pref[rr+1]++;
		}
		bool e=false;
		for(int i=1;i<=n;i++) e|=(!(pref[i]+=pref[i-1])&&ps[i]<=mid);
		if(e)
		{
			r=mid-1,ans=mid;
			continue;
		}
		for(int i=0;i<=n+1;i++) pref[i]=st[i];
		lt=rt=1;
		for(int i=1;i<=pl;i++)
		{
			while(C[lt]<A[i]-mid) lt++;
			while(C[rt]<=A[i]+mid) rt++;
			ll=max(i-rt+2,1),rr=min(i-lt+1,p[i]);
			if(ll<=rr) pref[ll]--,pref[rr+1]++;
		}
		lt=rt=1;
		for(int i=n*2-1;i>=pr;i--)
		{
			while(C[lt]<A[i]-mid) lt++;
			while(C[rt]<=A[i]+mid) rt++;
			ll=max(i-n+lt,p[i]),rr=min(i-n+rt-1,n);
			if(ll<=rr) pref[ll]--,pref[rr+1]++;
		}
		lt=rt=n;
		for(int i=1;i<=ql;i++)
		{
			while(B[rt]>A[i+n]+mid) rt--;
			while(B[lt]>=A[i+n]-mid) lt--;
			ll=max(i-n+lt+1,1),rr=min(i-n+rt,q[i]);
			if(ll<=rr) pref[ll]--,pref[rr+1]++;
		}
		lt=rt=n;
		for(int i=n*2-1;i>=qr;i--)
		{
			while(B[rt]>A[i-n]+mid) rt--;
			while(B[lt]>=A[i-n]-mid) lt--;
			ll=max(i-rt+1,q[i]),rr=min(i-lt,n);
			if(ll<=rr) pref[ll]--,pref[rr+1]++;
		}
		for(int i=1;i<=n;i++) e|=(!(pref[i]+=pref[i-1])&&qs[i]<=mid);
		if(e) r=mid-1,ans=mid;
		else l=mid+1;
	}
	cout<<ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 37 / 37
• Subtask 5: 33 / 33