Submission #1229956

#TimeUsernameProblemLanguageResultExecution timeMemory
1229956phtungSnowball (JOI21_ho_t2)C++20
100 / 100
90 ms8408 KiB
#include <bits/stdc++.h> using namespace std; #define int long long void solve() { int n, q; cin >> n >> q; vector<int> a(n + 2); a[0] = -1e18; a[n + 1] = 1e18; for (int i = 1; i <= n; ++i) cin >> a[i]; vector<int> shift(q + 1), mx(q + 2), mn(q + 2); int sum = 0; for (int i = 1; i <= q; ++i) { cin >> shift[i]; sum += shift[i]; mn[i] = min(mn[i - 1], sum); mx[i] = max(mx[i - 1], sum); } for (int i = 1; i <= n; ++i) { int res; int l = 0, r = q; while (l <= r) { int m = (l + r) / 2; if (a[i] + mx[m] <= a[i + 1] + mn[m]) { res = m; l = m + 1; } else { r = m - 1; } } int right = a[i] + mx[res]; if (res != q && shift[res + 1] > 0) right = a[i + 1] + mn[res]; l = 0, r = q; res = -1; while (l <= r) { int m = (l + r) / 2; if (a[i] + mn[m] >= a[i - 1] + mx[m]) { res = m; l = m + 1; } else { r = m - 1; } } int left = a[i] + mn[res]; if (res != q && shift[res + 1] < 0) left = a[i - 1] + mx[res]; cout << right - left << "\n"; } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...