Submission #1276435

#TimeUsernameProblemLanguageResultExecution timeMemory
1276435boclobanchatGrowing Vegetables is Fun 5 (JOI24_vegetables5)C++20
100 / 100
925 ms20464 KiB
#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]; int pf[MAXN],ps[MAXN],p[MAXN],pref[MAXN]; int qf[MAXN],qs[MAXN],q[MAXN],qref[MAXN]; 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]; sort(B+1,B+n+1); sort(C+1,C+n+1); 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;i++) D[i]=A[i+n],D[i+n]=A[i]; for(int i=0;i<n*2;i++) p[i]=q[i]=0; 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) 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) 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]),qf[1]=abs(B[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]])); qf[i]=max(qf[i-1],abs(B[i]-D[L[i]])); } else { R[i]++; pf[i]=max(pf[i-1],abs(C[i]-D[R[i]])); qf[i]=max(qf[i-1],abs(B[i]-D[R[i]])); } } 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) 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) 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=INF,ans=INF,ll,rr; while(l<=r) { int mid=(l+r)/2; for(int i=0;i<=n+1;i++) pref[i]=0; lt=rt=1; for(int i=1;p[i];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]++; pref[1]++,pref[p[i]+1]--; } lt=rt=1; for(int i=n*2-1;p[i];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]++; pref[p[i]]++; } lt=rt=n; for(int i=1;q[i];i++) { while(C[rt]>D[i]+mid) rt--; while(C[lt]>=D[i]-mid) lt--; ll=max(i-n+lt+1,1),rr=min(i-n+rt,q[i]); if(ll<=rr) pref[ll]--,pref[rr+1]++; pref[1]++,pref[q[i]+1]--; } lt=rt=n; for(int i=n*2-1;q[i];i--) { while(C[rt]>D[i]+mid) rt--; while(C[lt]>=D[i]-mid) lt--; ll=max(i-rt+1,q[i]),rr=min(i-lt,n); if(ll<=rr) pref[ll]--,pref[rr+1]++; pref[q[i]]++; } 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]=0; lt=rt=1; for(int i=1;p[i];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]++; pref[1]++,pref[p[i]+1]--; } lt=rt=1; for(int i=n*2-1;p[i];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]++; pref[p[i]]++; } lt=rt=n; for(int i=1;q[i];i++) { while(B[rt]>D[i]+mid) rt--; while(B[lt]>=D[i]-mid) lt--; ll=max(i-n+lt+1,1),rr=min(i-n+rt,q[i]); if(ll<=rr) pref[ll]--,pref[rr+1]++; pref[1]++,pref[q[i]+1]--; } lt=rt=n; for(int i=n*2-1;q[i];i--) { while(B[rt]>D[i]+mid) rt--; while(B[lt]>=D[i]-mid) lt--; ll=max(i-rt+1,q[i]),rr=min(i-lt,n); if(ll<=rr) pref[ll]--,pref[rr+1]++; pref[q[i]]++; } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...