Submission #862010

#TimeUsernameProblemLanguageResultExecution timeMemory
8620108pete8Snowball (JOI21_ho_t2)C++14
0 / 100
2 ms528 KiB
#include<iostream> #include<stack> #include<map> #include<vector> #include<string> #include<unordered_map> #include <queue> #include<cstring> #include<limits.h> #include<cmath> #include<set> #include<algorithm> #include<bitset> #include<stack> using namespace std; #define ll long long #define f first #define endl "\n" #define s second #define pii pair<int,int> #define pppiiii pair<pii,pii> #define ppii pair<int,pii> #define all(x) x.begin(),x.end() #define pb push_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define fastio ios::sync_with_stdio(false);cin.tie(NULL); #define int long long const int mxn=5e5+10,mx=5e6+10,minf=-1e9; int32_t main(){ int n,q;cin>>n>>q; vector<int>pos(n),ans(n,0); for(int i=0;i<n;i++)cin>>pos[i]; vector<int>mn(q,0),mx(q,0); int cur=0; for(int i=1;i<=q;i++){ int k;cin>>k; cur+=k; if(i)mn[i]=mn[i-1],mx[i]=mx[i-1]; mn[i]=min(mn[i],cur); mx[i]=max(mx[i],cur); } ans[0]-=mn[q]; ans[n-1]+=mx[q]; for(int i=0;i<n-1;i++){ int l=0,r=q,a=0; while(l<=r){ int mid=l+(r-l)/2; if(pos[i+1]+mn[mid]>pos[i]+mx[mid]){ a=max(a,mid); l=mid+1; } else r=mid-1; } ans[i]+=mx[a]; ans[i+1]-=mn[a]; if(a<q){ int diff=(pos[i+1]+mn[a])-(pos[i]+mx[a]); if(mx[a+1]>mx[a])ans[i]+=diff; else ans[i+1]+=diff; } } for(auto i:ans)cout<<i<<'\n'; } /* 4 5 3 100 2 80 100 5 125 130 4 75 150 3 120 110 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...