Submission #810563

#TimeUsernameProblemLanguageResultExecution timeMemory
810563winter0101Snowball (JOI21_ho_t2)C++14
100 / 100
939 ms16936 KiB
#include<bits/stdc++.h> using namespace std; #define all(fl) fl.begin(),fl.end() #define pb push_back #define fi first #define se second #define for1(i,j,k) for(int i=j;i<=k;i++) #define for2(i,j,k) for(int i=j;i>=k;i--) #define for3(i,j,k,l) for(int i=j;i<=k;i+=l) #define lb lower_bound #define ub upper_bound #define sz(a) (int)a.size() #define pii pair<int,int> #define pli pair<long long,int> #define gcd __gcd #define lcm(x,y) x*y/__gcd(x,y) #define pil pair<int,long long> #define pll pair<long long,long long> #define eb emplace_back const int maxn=2e5+9; long long x[maxn],w[maxn],a[maxn],b[maxn],c[maxn]; long long ans[maxn]; int n,q; signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); //freopen("temp.INP","r",stdin); //freopen("temp.OUT","w",stdout); cin>>n>>q; for1(i,1,n)cin>>x[i]; for1(i,1,q){ cin>>w[i]; a[i]=a[i-1]+w[i]; b[i]=max(a[i],b[i-1]); c[i]=min(a[i],c[i-1]); } for1(i,1,n){ if (i==n){ if (b[q]>0)ans[i]+=b[q]; continue; } long long l=x[i],r=x[i+1]; while (l<=r){ long long mid=(l+r)/2; //cerr<<mid<<'\n'; if (b[q]+x[i]<mid){ r=mid-1; } else { int l1=1,r1=q,c1=-1; while (l1<=r1){ int mid1=(l1+r1)/2; if (x[i]+b[mid1]>=mid){ c1=mid1; r1=mid1-1; } else l1=mid1+1; } if (x[i+1]+c[c1]<mid){ r=mid-1; } else { l=mid+1; ans[i]=mid-x[i]; } } } //cout<<ans[i]<<'\n'; } //return 0; for1(i,1,n){ if (i==1){ if (c[q]<0)ans[i]-=c[q]; continue; } long long l=x[i-1],r=x[i],s=x[i]; while (l<=r){ long long mid=(l+r)/2; if (x[i]+c[q]>mid){ l=mid+1; } else { int l1=1,r1=q,c1=-1; while (l1<=r1){ int mid1=(l1+r1)/2; if (x[i]+c[mid1]<=mid){ c1=mid1; r1=mid1-1; } else l1=mid1+1; } if (x[i-1]+b[c1]>mid){ l=mid+1; } else { r=mid-1; s=mid; } } } ans[i]+=x[i]-s; //ans[i]=s; //cout<<ans[i]<<'\n'; } //cout<<ans[2]; for1(i,1,n)cout<<ans[i]<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...