Submission #1230490

#TimeUsernameProblemLanguageResultExecution timeMemory
1230490harryleeeSnowball (JOI21_ho_t2)C++20
100 / 100
86 ms9800 KiB
#include<bits/stdc++.h> using namespace std; const int maxn = 2e5; const long long inf = 1e18; int n, q; long long a[maxn + 1], v[maxn + 1], mx[maxn + 1], mn[maxn + 1], ans[maxn + 1]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> q; for (int i = 1; i <= n; ++i) cin >> a[i]; long long sum = 0; for (int i = 1; i <= q; ++i){ cin >> v[i]; sum += v[i]; mx[i] = max(mx[i - 1], sum); mn[i] = min(mn[i - 1], sum); } for (int i = 1; i <= n; ++i){ int lo = 1, hi = q; long long res = 0; while (lo <= hi){ int m = (lo + hi) >> 1; long long lb = a[i] + mn[m], rb = (i == 1) ? -inf : a[i - 1] + mx[m]; res = max(res, a[i] - max(lb, rb)); if (lb > rb) lo = m + 1; else hi = m - 1; } ans[i] += res; lo = 1, hi = q, res = 0; while (lo <= hi){ int m = (lo + hi) >> 1; long long rb = a[i] + mx[m], lb = (i == n) ? inf : a[i + 1] + mn[m]; res = max(res, min(lb, rb) - a[i]); if (rb < lb) lo = m + 1; else hi = m - 1; } ans[i] += res; } for (int i = 1; i <= n; ++i) cout << ans[i] << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...