Submission #881784

#TimeUsernameProblemLanguageResultExecution timeMemory
881784AlphaMale06Snowball (JOI21_ho_t2)C++14
100 / 100
104 ms20640 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define F first #define S second #define mp make_pair signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; int a[n], b[q]; for(int i=0; i< n; i++)cin >> a[i]; for(int i=0; i< q; i++)cin >> b[i]; vector<pair<int, int>> lr; vector<pair<int, int>> del; lr.pb({0, 0}); del.pb({0, 0}); int sum=0; for(int i=0; i< q; i++){ sum+=b[i]; pair<int, int> nxt; if(sum < 0){ nxt.F=max(-sum, lr[i].F); nxt.S=lr[i].S; } else{ nxt.F=lr[i].F; nxt.S=max(sum, lr[i].S); } lr.pb(nxt); del.pb({nxt.F+nxt.S, i+1}); } int ans[n][2]; for(int i=1; i< n; i++){ int dlt=a[i]-a[i-1]; auto itr=upper_bound(del.begin(), del.end(), mp(dlt, -1ll)); if(itr==del.end()){ ans[i][0]=lr[q].F; ans[i-1][1]=lr[q].S; } else{ itr--; int ind = (*itr).S; ans[i][0]=min(dlt, lr[ind].F); ans[i-1][1]=min(dlt, lr[ind].S); if(lr[ind+1].F>lr[ind].F){ ans[i][0]=dlt-ans[i-1][1]; } else{ ans[i-1][1]=dlt-ans[i][0]; } } } ans[0][0]=lr[q].F; ans[n-1][1]=lr[q].S; for(int i=0; i< n; i++){ cout << ans[i][0]+ans[i][1] << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...