Submission #523329

#TimeUsernameProblemLanguageResultExecution timeMemory
523329lucriSnowball (JOI21_ho_t2)C++17
33 / 100
192 ms9500 KiB
#include <iostream> #include <cmath> using namespace std; long long n,q,x[200010],ans[200010],mp[200010],w,cnt,dmin,dmax; long long cb(long long b,long long e,long long val) { while(b<=e) { long long m=(b+e)/2; if(mp[m-1]-mp[m]<val&&mp[m]-mp[m-1]<val) b=m+1; else e=m-1; } return b; } int main() { cin>>n>>q; for(long long i=1;i<=n;++i) { cin>>x[i]; } long long dp=0; for(long long i=1;i<=q;++i) { cin>>w; dp+=w; if(dp<0) { if(mp[cnt]<0) { if(dp<mp[cnt]) mp[cnt]=dp; } else { if(dp<dmin) { mp[++cnt]=dp; dmin=dp; } } } else if(dp>0) { if(mp[cnt]>0) { if(dp>mp[cnt]) mp[cnt]=dp; } else { if(dp>dmax) { mp[++cnt]=dp; dmax=dp; } } } } if(mp[cnt]<0) { ans[1]-=mp[cnt]; ans[n]+=mp[cnt-1]; } else { ans[1]-=mp[cnt-1]; ans[n]+=mp[cnt]; } for(long long i=1;i<n;++i) { long long b=cb(1,cnt,x[i+1]-x[i]); if(b>cnt) { if(mp[cnt]<0) { ans[i+1]-=mp[cnt]; ans[i]+=mp[cnt-1]; } else { ans[i+1]-=mp[cnt-1]; ans[i]+=mp[cnt]; } } else { if(mp[b]<0) { ans[i]+=mp[b-1]; ans[i+1]+=x[i+1]-x[i]-mp[b-1]; } else { ans[i+1]-=mp[b-1]; ans[i]+=x[i+1]-x[i]+mp[b-1]; } } } for(long long i=1;i<=n;++i) { cout<<ans[i]<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...