제출 #1276389

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276389		boclobanchat	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	100 / 100	1108 ms	22788 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int MAXN=6e5+5;
const int INF=1e9;
int A[MAXN],D[MAXN],B[MAXN],C[MAXN],L[MAXN],R[MAXN],pref[MAXN];
int pf[MAXN],p[MAXN],ps[MAXN];
int qf[MAXN],q[MAXN],qs[MAXN];
bool ck[MAXN];
int solve(int n)
{
	int pt,lt,rt;
	L[1]=R[1]=n+1,pf[1]=abs(B[n]-A[n+1]);
	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]]));
		else R[i]++,pf[i]=max(pf[i-1],abs(B[n-i+1]-A[R[i]]));
	}
	for(int i=1;i<=n*2;i++) p[i]=q[i]=-1;
	pt=1;
	for(int i=2;i<=n+1;i++)
	{
		while(pt<=n&&i<=L[pt]&&R[pt]<=i+n-1) pt++;
		ps[i]=pf[--pt];
		if(i==2) lt=i,rt=L[pt]-1;
		else
		{
			while(lt<i) p[lt]=i-1,lt++;
			while(rt>L[pt]-1) p[rt]=i-1,rt--;
		}
		if(pt==n) break;
		pt++;
	}
	pt=1;
	for(int i=n+1;i>=2;i--)
	{
		while(pt<=n&&i<=L[pt]&&R[pt]<=i+n-1) pt++;
		ps[i]=pf[--pt];
		if(i==n+1) lt=R[pt]+1,rt=i+n-1;
		else
		{
			while(lt<R[pt]+1) p[lt]=i+1,lt++;
			while(rt>i+n-1) p[rt]=i+1,rt--;
		}
		if(pt==n) break;
		pt++;
	}
	for(int i=1;i<=n;i++) D[i]=A[i+n],D[i+n]=A[i];
	L[1]=R[1]=n+1,qf[1]=abs(C[1]-D[n+1]);
	for(int i=2;i<=n;i++)
	{
		L[i]=L[i-1],R[i]=R[i-1];
		if(D[L[i]-1]<D[R[i]+1]) L[i]--,qf[i]=max(qf[i-1],abs(C[i]-D[L[i]]));
		else R[i]++,qf[i]=max(qf[i-1],abs(C[i]-D[R[i]]));
	}
	pt=1;
	for(int i=2;i<=n+1;i++)
	{
		while(pt<=n&&i<=L[pt]&&R[pt]<=i+n-1) pt++;
		qs[i]=qf[--pt];
		if(i==2) lt=i,rt=L[pt]-1;
		else
		{
			while(lt<i) q[lt]=i-1,lt++;
			while(rt>L[pt]-1) q[rt]=i-1,rt--;
		}
		if(pt==n) break;
		pt++;
	}
	pt=1;
	for(int i=n+1;i>=2;i--)
	{
		while(pt<=n&&i<=L[pt]&&R[pt]<=i+n-1) pt++;
		qs[i]=qf[--pt];
		if(i==n+1) lt=R[pt]+1,rt=i+n-1;
		else
		{
			while(lt<R[pt]+1) q[lt]=i+1,lt++;
			while(rt>i+n-1) q[rt]=i+1,rt--;
		}
		if(pt==n) break;
		pt++;
	}
	int l=0,r=INF,ans=INF;
	while(l<=r)
	{
		int mid=l+(r-l)/2;
		lt=rt=1;
		for(int i=0;i<=n+2;i++) pref[i]=0;
		for(int i=2;i<=n;i++) if(p[i]!=-1)
		{
			while(lt<=n&&B[lt]<A[i]-mid) lt++;
			while(rt<=n&&B[rt]<=A[i]+mid) rt++;
			int L=max(i-rt+2,2),R=min(i-lt+1,p[i]);
			if(L<=R) pref[L]--,pref[R+1]++;
			pref[2]++,pref[p[i]+1]--;
		}
		lt=rt=1;
		for(int i=n*2;i>=n+2;i--) if(p[i]!=-1)
		{
			while(lt<=n&&B[lt]<A[i]-mid) lt++;
			while(rt<=n&&B[rt]<=A[i]+mid) rt++;
			int L=max(i-n+lt,p[i]),R=min(i-n+rt-1,n+1);
			if(L<=R) pref[L]--,pref[R+1]++;
			pref[p[i]]++,pref[n+2]--;
		}
		lt=rt=n;
		for(int i=2;i<=n;i++) if(q[i]!=-1)
		{
			while(rt>=1&&C[rt]>D[i]+mid) rt--;
			while(lt>=1&&C[lt]>=D[i]-mid) lt--;
			int L=max(i-n+lt+1,2),R=min(i-n+rt,q[i]);
			if(L<=R) pref[L]--,pref[R+1]++;
			pref[2]++,pref[q[i]+1]--;
		}
		lt=rt=n;
		for(int i=n*2;i>=n+2;i--) if(q[i]!=-1)
		{
			while(rt>=1&&C[rt]>D[i]+mid) rt--;
			while(lt>=1&&C[lt]>=D[i]-mid) lt--;
			int L=max(i-rt+1,q[i]),R=min(i-lt,n+1);
			if(L<=R) pref[L]--,pref[R+1]++;
			pref[q[i]]++,pref[n+2]--;
		}
		bool e=false;
		for(int i=2;i<=n+1;i++) e|=(!(pref[i]+=pref[i-1])&&ps[i]<=mid&&qs[i]<=mid);
		if(e) r=mid-1,ans=mid;
		else l=mid+1;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	for(int i=1;i<=n*2;i++) cin>>A[i];
	for(int i=1;i<=n;i++) cin>>B[i];
	for(int i=1;i<=n;i++) cin>>C[i];
	sort(B+1,B+n+1);
	sort(C+1,C+n+1);
	int ans=solve(n);
	swap(B,C);
	ans=min(ans,solve(n));
	cout<<ans;
}

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