Submission #1039304

#TimeUsernameProblemLanguageResultExecution timeMemory
1039304DucNguyen2007Snowball (JOI21_ho_t2)C++14
33 / 100
2549 ms8644 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define ld long double #define pii pair<int,int> #define pll pair<ll,ll> #define fi first #define se second const int maxN=2e5+5; const ll inf=2e18; int n,q; pll b[maxN+1]; ll x[maxN+1],a[maxN+1],w[maxN+1],l[maxN+1],r[maxN+1]; int main() { //freopen("","r",stdin); //freopen("","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>q; for(int i=1;i<=n;i++) { cin>>x[i]; } for(int i=1;i<=q;i++) { cin>>w[i]; } ll val=0; for(int j=1;j<=q;j++) { val+=w[j]; for(int i=1;i<=n;i++) { l[i]=max(l[i],val); r[i]=max(r[i],-val); } //cout<<j<<'\n'; for(int i=1;i<n;i++) { ll tmp=x[i+1]-x[i]; //cout<<i<<" "<<tmp<<" "<<l[i]<<" "<<r[i+1]<<'\n'; if(l[i]+r[i+1]<=tmp) { b[i].fi=l[i]; b[i].se=r[i+1]; } else { ll pre_l=b[i].fi,pre_r=b[i].se; ll cur=tmp-pre_l-pre_r; if(val>0) { b[i].fi+=cur; } else b[i].se+=cur; } } } //cout<<b[1].fi<<'\n'; for(int i=1;i<=n;i++) { if(i<n) { a[i]+=b[i].fi; a[i+1]+=b[i].se; } if(i==1) { a[i]+=r[i]; } if(i==n) { a[i]+=l[i]; } cout<<a[i]<<'\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...