Submission #974270

#TimeUsernameProblemLanguageResultExecution timeMemory
974270happy_nodeSeesaw (JOI22_seesaw)C++17
100 / 100
169 ms29376 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; const int MX=2e5+5; int N; ll A[MX]; ld f(int l, int r) { return (ld)(A[r]-A[l-1])/(r-l+1); } vector<pair<ld,int>> v; ld L[MX], R[MX]; int idL[MX], idR[MX]; struct fenwick { int t[2*MX]; void upd(int pos, int val) { for(int i=pos;i<=2*N;i+=i&-i) t[i]+=val; } int que(int pos) { int res=0; for(int i=pos;i>0;i-=i&-i) res+=t[i]; return res; } int que(int l, int r) { return que(r)-que(l-1); } } fw; int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin>>N; for(int i=1;i<=N;i++) { cin>>A[i]; A[i]+=A[i-1]; } for(int k=1;k<=N;k++) { int l=k,r=N,res=0; while(l<=r) { int mid=(l+r)/2; if(f(mid-k+1,mid)>=f(1,N)) { res=mid,r=mid-1; } else { l=mid+1; } } // f(res-k,res-1) or f(res-k+1,res) if(res-k<1) L[k]=f(res-k+1,res); else L[k]=f(res-k,res-1); R[k]=f(res-k+1,res); v.push_back({L[k],k}); v.push_back({R[k],k}); } sort(v.begin(),v.end()); int id=1; for(auto [x,k]:v) { if(!idL[k]) idL[k]=id; else idR[k]=id; id++; } for(int k=1;k<=N;k++) fw.upd(idL[k],1); /* each k adds 2 important point f(l,l+k-1) or f(l+1,l+k) for some l s.t. f(l,l+k-1) <= f(1,N) <= f(l+1,l+k) a range [L,R] is valid iff every k in [1,N] exist atleast one important point we can show sufficiency by noticing that (*) f(l,r) < f(l+1,r+1) < f(l+2,r+2) < ... also notice that important points are two consecutive terms in (*) now plot each f(l,r) in a similar fashion to pascal's triangle where each row groups all ranges with same length assume we reach the k-th row and want to go down to (k+1) th row if we're in the left imp. point of k-th row which is in [L,R] the option is to either go to the left imp. point of (k+1)-th row of right imp. point if left imp. point is in [L,R] we are done if left imp. point isn't in [L,R] then it must either be in [1,L) or (R,N] if it is in (R,N], this is absurd due to our assumption that there exist an imp point of range (k+1) in [L,R] if it is in [1,L), then the right imp. point must be in [L,R] so we can go there and we are done. this is because since we are in left imp. point of k-th row it can produce to imp. point in k+1 th row also notice that f(l,r-1) < f(l,r) < f(l+1,r) so what it produces is one is to its left and one is to its right since one is already to its left, the other one must be to its right */ ld ans=2e18; for(auto [x,k]:v) { int l=1,r=2*N,res=0; while(l<=r) { int mid=(l+r)/2; if(fw.que(mid)==N) { r=mid-1,res=mid; } else { l=mid+1; } } if(res!=0) { ans=min(ans,v[res-1].first-x); } if(idL[k]) { fw.upd(idL[k],-1); fw.upd(idR[k],1); idL[k]=0; } else { fw.upd(idR[k],-1); } } cout<<fixed<<setprecision(10)<<ans<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...