Submission #1032006

#TimeUsernameProblemLanguageResultExecution timeMemory
1032006mnieplowiczSnowball (JOI21_ho_t2)C++14
100 / 100
81 ms15416 KiB
#include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n, q; cin >> n >> q; int n1 = n + 1, q1 = q + 1; vector<long long> v(n1), mini(q1, 0), maxi(q1, 0), Q(q1); for(int i = 1; i <= n; i++) cin >> v[i]; long long sum = 0; for(int i = 1; i <= q; i++){ cin >> Q[i]; sum += Q[i]; /*if(i == 0){ mini[i] = min(0ll, sum); maxi[i] = max(0ll, sum); continue; }*/ mini[i] = min(mini[i - 1], sum); maxi[i] = max(maxi[i - 1], sum); } /*for(int i = 0; i <q; i++) cout << mini[i] << " "; cout << '\n'; for(int i = 0; i <q; i++) cout << maxi[i] << " "; cout << '\n';*/ auto bs = [&](int i){ int l = 0, r = q + 1; while(l + 1 < r){ int mid = (l + r) / 2; if(v[i + 1] - v[i] >= maxi[mid] - mini[mid]) l = mid; else r = mid; } return l; }; vector<long long> res(n1); for(int i = 1; i < n; i++){ int x = bs(i); //cerr << i << ": " << x <<" " << mini[x] << " " << maxi[x]<< '\n'; res[i] += maxi[x]; res[i + 1] -= mini[x]; long long dif = 0; if(x != q) dif = v[i + 1] - v[i] - (maxi[x] - mini[x]); if(dif and Q[x + 1] > 0) res[i] += dif; if(dif and Q[x + 1] <= 0) res[i + 1] += dif; //cerr << res[i] << " " << res[i+1] << '\n'; } res[1] -= mini[q]; res[n] += maxi[q]; for(int a = 1; a <= n; a++) cout << res[a] << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...