#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=3e5+5;
const int base=(1<<15)-1;
const int INF=1e9;
int A[MAXN*2],D[MAXN*2],B[MAXN],C[MAXN],L[MAXN],R[MAXN],pref[MAXN],pf[MAXN],p[MAXN*2],q[MAXN*2],ps[MAXN],st[MAXN],posa[MAXN*2],posb[MAXN*2];
struct countingsort
{
int cnt[(1<<15)+15],curr[MAXN];
void csort(int arr[],int n)
{
for(int i=1;i<=n;i++) cnt[arr[i]&base]++;
for(int i=1;i<=base;i++) cnt[i]+=cnt[i-1];
for(int i=n;i;i--) curr[cnt[arr[i]&base]--]=arr[i];
for(int i=1;i<=base;i++) cnt[i]=0;
for(int i=1;i<=n;i++) cnt[curr[i]>>15]++;
for(int i=1;i<base;i++) cnt[i]+=cnt[i-1];
for(int i=n;i;i--) arr[cnt[curr[i]>>15]--]=curr[i];
for(int i=1;i<base;i++) cnt[i]=0;
}
};
countingsort f;
int solve(int n)
{
int pt,lt,rt;
B[0]=C[0]=-INF*2-7,B[n+1]=C[n+1]=INF*2+7;
for(int i=0;i<n*2;i++) p[i]=q[i]=st[i]=0;
for(int i=0;i<n;i++) D[i]=A[i+n],D[i+n]=A[i];
L[1]=R[1]=n,pf[1]=abs(B[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]]));
else R[i]++,pf[i]=max(pf[i-1],abs(B[n-i+1]-A[R[i]]));
}
pt=1;
for(int i=1;;i++)
{
while(i<=L[pt]&&R[pt]<=i+n-1) pt++;
ps[i]=pf[--pt];
if(i==1) 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++;
ps[i]=pf[--pt];
if(i==n) 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]-D[n]);
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]--,pf[i]=max(pf[i-1],abs(C[i]-D[L[i]]));
else R[i]++,pf[i]=max(pf[i-1],abs(C[i]-D[R[i]]));
}
pt=1;
for(int i=1;;i++)
{
while(i<=L[pt]&&R[pt]<=i+n-1) pt++;
ps[i]=max(ps[i],pf[--pt]);
if(i==1) 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++;
ps[i]=max(ps[i],pf[--pt]);
if(i==n) lt=R[pt]+1;
else
{
while(lt<=R[pt]) q[lt++]=i+1;
q[i+n]=i+1;
}
if(pt==n) break;
pt++;
}
int l=0,r=0,ans=INF,ll,rr,cnta=0,cntb=0,lt2=1,rt2=n*2-1;
for(int i=1;i<=n;i++) r=max(r,ps[i]);
for(int i=1;p[i];i++) st[1]++,st[p[i]+1]--;
for(int i=n*2-1;p[i];i--) st[p[i]]++,st[n+1]--;
for(int i=1;q[i];i++) st[1]++,st[q[i]+1]--;
for(int i=n*2-1;q[i];i--) st[q[i]]++,st[n+1]--;
while(p[lt2]||p[rt2]) if(!p[rt2]||(p[lt2]&&A[lt2]<A[rt2])) posa[++cnta]=lt2++;
else posa[++cnta]=rt2--;
lt2=1,rt2=n*2-1;
while(q[lt2]||q[rt2]) if(!q[rt2]||(q[lt2]&&D[lt2]>D[rt2])) posb[++cntb]=lt2++;
else posb[++cntb]=rt2--;
while(l<=r)
{
int mid=l+(r-l)/2;
lt=rt=1;
for(int i=0;i<=n+1;i++) pref[i]=st[i];
for(int i=1;i<=cnta;i++)
{
int z=posa[i];
while(B[lt]+mid<A[z]) lt++;
while(B[rt]-mid<=A[z]) rt++;
if(z<n) ll=max(z-rt+2,1),rr=min(z-lt+1,p[z]);
else ll=max(z-n+lt,p[z]),rr=min(z-n+rt-1,n);
if(ll<=rr) pref[ll]--,pref[rr+1]++;
}
lt=rt=n;
for(int i=1;i<=cntb;i++)
{
int z=posb[i];
while(C[rt]-mid>D[z]) rt--;
while(C[lt]+mid>=D[z]) lt--;
if(z<n) ll=max(z+lt-n+1,1),rr=min(z-n+rt,q[z]);
else ll=max(z-rt+1,q[z]),rr=min(z-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;
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=0;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];
f.csort(B,n);
f.csort(C,n);
int ans=solve(n);
swap(B,C);
ans=min(ans,solve(n));
cout<<ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |