Submission #1080953

#TimeUsernameProblemLanguageResultExecution timeMemory
1080953IcelastSnowball (JOI21_ho_t2)C++17
100 / 100
103 ms20068 KiB
#include <iostream> #include <bits/stdc++.h> #define ll long long using namespace std; const ll maxn = 2*1e5+5, INF = 4e18+9; void solve(){ ll n, Q; cin >> n >> Q; vector<ll> a(n+2), q(Q+1); a[0] = -1e18; a[n+1] = 1e18; for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 1; i <= Q; i++){ cin >> q[i]; } vector<pair<ll, ll>> b(n+1); for(int i = 1; i <= n; i++){ b[i] = {a[i]-a[i-1], a[i+1]-a[i]}; } vector<ll> mn(Q+1, 0), mx(Q+1, 0); ll sum = 0; for(int i = 1; i <= Q; i++){ sum += q[i]; mn[i] = mn[i-1]; mx[i] = mx[i-1]; if(sum > mx[i]){ mx[i] = sum; } if(sum < mn[i]){ mn[i] = sum; } } vector<ll> f(Q+1); for(int i = 1; i <= Q; i++){ f[i] = mx[i]-mn[i]; } vector<ll> ans(n+1, 0); for(int i = 1; i <= n; i++){ int l, r, mid; ll x; l = 1; r = Q; x = b[i].first; while(l <= r){ mid = (l+r)/2; if(x <= f[mid]){ r = mid-1; }else{ l = mid+1; } } //cout << l << " " << f[l] << " " << x << " " << mn[l] << "\n"; if(l == Q+1){ ans[i] += mn[Q]*-1; }else{ if(mn[l] != mn[l-1]){ ans[i] += mn[l]*-1-(f[l]-x); }else{ ans[i] += mn[l]*-1; } } //cout << ans[i] << "\n"; l = 1; r = Q; x = b[i].second; while(l <= r){ mid = (l+r)/2; if(x <= f[mid]){ r = mid-1; }else{ l = mid+1; } } //cout << l << " " << f[l] << " " << x << " " << mx[l] << "\n"; if(l == Q+1){ ans[i] += mx[Q]; }else{ if(mx[l] != mx[l-1]){ ans[i] += mx[l]-(f[l]-x); }else{ ans[i] += mx[l]; } } } for(int i = 1; i <= n; i++){ cout << ans[i] << "\n"; } } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...