Submission #856865

#TimeUsernameProblemLanguageResultExecution timeMemory
856865StefanSebezSnowball (JOI21_ho_t2)C++14
100 / 100
172 ms20144 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define ll long long const ll inf=1e17+50000; int main() { ll n,q;cin>>n>>q; ll a[n+1];for(ll i=1;i<=n;i++)cin>>a[i]; ll w[q+1],pref[q+1]={0},mn[q+1],maks[q+1]; mn[0]=inf; maks[0]=-inf; /*map<int,int>mapa; set<int>st;*/ for(ll i=1;i<=q;i++) { cin>>w[i]; pref[i]=pref[i-1]+w[i]; mn[i]=min(mn[i-1],pref[i]); maks[i]=max(maks[i-1],pref[i]); //if(pref[i]>=0) st.insert(pref[i]); } /*for(int i=q;i>=1;i--) mapa[pref[i]]=i; vector<int>b; while(!st.empty()) { int x=*st.begin(); b.pb(x); st.erase(x); } for(auto i:b) printf("%i ",i); printf("\n"); for(int i=1;i<=q;i++) printf("%i: %i %i\n",i,mn[i],maks[i]);*/ ll L[n+1]={0},R[n+1]={0}; for(ll i=1;i<n;i++) { ll l=1,r=q,mid=(l+r)/2,ind=0; while(l<=r) { ll x=maks[mid],y=-mn[mid]; if(x<0) x=0; if(y<0) y=0; if(a[i+1]-a[i]>=x+y) { R[i]=x; L[i+1]=y; l=mid+1; } else { ind=mid; r=mid-1; } mid=(l+r)/2; } if(ind==0) continue; if(pref[ind]>=0) R[i]=a[i+1]-a[i]-L[i+1]; else L[i+1]=a[i+1]-a[i]-R[i]; /*int l=0,r=lower_bound(b.begin(),b.end(),a[i+1]-a[i]+1)-b.begin()-1,mid=(l+r)/2; while(l<=r) { int j=mapa[b[mid]]; printf("%i %i %i %i: %i %i\n",i,l,mid,r,b[mid],j); if(a[i]+b[mid]<=a[i+1]+mn[j]) { R[i]=b[mid]; l=mid+1; } else r=mid-1; mid=(l+r)/2; }*/ } R[n]=maks[q];if(R[n]<0) R[n]=0; L[1]=-mn[q];if(L[1]<0) L[1]=0; /*for(int i=2;i<=n;i++) { if(mn[q]>=0) {L[i]=0;continue;} L[i]=min(-mn[q],a[i]-a[i-1]-R[i-1]); }*/ /*for(int i=1;i<=n;i++) cout<<L[i]<<" "; printf("\n"); for(int i=1;i<=n;i++) cout<<R[i]<<" "; printf("\n");*/ ll res[n+1]={0}; for(ll i=1;i<=n;i++) { res[i]=R[i]+L[i]; cout<<res[i]<<" "; } printf("\n"); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...