Submission #1276430

#TimeUsernameProblemLanguageResultExecution timeMemory
1276430boclobanchatGrowing Vegetables is Fun 5 (JOI24_vegetables5)C++20
100 / 100
1139 ms27624 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],pref[MAXN]; int pf[MAXN],pl[MAXN],pr[MAXN],ps[MAXN]; int qf[MAXN],ql[MAXN],qr[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++) pl[i]=pr[i]=ql[i]=qr[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) pl[lt]=2,pr[lt]=i-1,lt++; while(rt>L[pt]-1) pl[rt]=2,pr[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) pl[lt]=i+1,pr[lt]=n+1,lt++; while(rt>i+n-1) pl[rt]=i+1,pr[rt]=n+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) ql[lt]=2,qr[lt]=i-1,lt++; while(rt>L[pt]-1) ql[rt]=2,qr[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) ql[lt]=i+1,qr[lt]=n+1,lt++; while(rt>i+n-1) ql[rt]=i+1,qr[rt]=n+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(pl[i]!=-1) { while(lt<=n&&B[lt]<A[i]-mid) lt++; while(rt<=n&&B[rt]<=A[i]+mid) rt++; rt--; int L=max(i-rt+1,pl[i]),R=min(i-lt+1,pr[i]); if(L<=R) pref[L]--,pref[R+1]++; pref[pl[i]]++,pref[pr[i]+1]--; rt++; } lt=rt=1; for(int i=n*2;i>=n+2;i--) if(pl[i]!=-1) { while(lt<=n&&B[lt]<A[i]-mid) lt++; while(rt<=n&&B[rt]<=A[i]+mid) rt++; rt--; int L=max(i-n+lt,pl[i]),R=min(i-n+rt,pr[i]); if(L<=R) pref[L]--,pref[R+1]++; pref[pl[i]]++,pref[pr[i]+1]--; rt++; } lt=rt=n; for(int i=2;i<=n;i++) if(ql[i]!=-1) { while(rt>=1&&C[rt]>D[i]+mid) rt--; while(lt>=1&&C[lt]>=D[i]-mid) lt--; lt++; int L=max(i-n+lt,ql[i]),R=min(i-n+rt,qr[i]); if(L<=R) pref[L]--,pref[R+1]++; pref[ql[i]]++,pref[qr[i]+1]--; lt--; } lt=rt=n; for(int i=n*2;i>=n+2;i--) if(ql[i]!=-1) { while(rt>=1&&C[rt]>D[i]+mid) rt--; while(lt>=1&&C[lt]>=D[i]-mid) lt--; lt++; int L=max(i-rt+1,ql[i]),R=min(i-lt+1,qr[i]); if(L<=R) pref[L]--,pref[R+1]++; pref[ql[i]]++,pref[qr[i]+1]--; lt--; } 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; }
#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...