Submission #704647

#TimeUsernameProblemLanguageResultExecution timeMemory
704647StickfishSnowball (JOI21_ho_t2)C++17
100 / 100
224 ms15284 KiB
#include <iostream> #include <vector> using namespace std; using ll = long long; const int MAXN = 2e5 + 123; ll a[MAXN]; ll w[MAXN]; pair<ll, ll> sg_[MAXN]; pair<ll, ll>* sg = sg_ + 1; signed main() { int n, q; cin >> n >> q; for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < q; ++i) cin >> w[i]; ll rx = 0; for (int i = 0; i < q; ++i) { rx += w[i]; sg[i] = sg[i - 1]; sg[i].first = min(sg[i].first, rx); sg[i].second = max(sg[i].second, rx); } vector<ll> ans(n); ll len = sg[q - 1].second - sg[q - 1].first; ans[0] = -sg[q - 1].first; ans[n - 1] = sg[q - 1].second; for (int i = 0; i + 1 < n; ++i) { if (a[i + 1] - a[i] >= len) { ans[i] += sg[q - 1].second; ans[i + 1] += -sg[q - 1].first; } else { int lb = -1, ub = q; while (ub - lb > 1) { int mb = (lb + ub) / 2; if (a[i + 1] - a[i] >= sg[mb].second - sg[mb].first) lb = mb; else ub = mb; } ans[i] += sg[lb].second; ans[i + 1] += -sg[lb].first; if (w[lb + 1] > 0) ans[i] += a[i + 1] - a[i] - sg[lb].second + sg[lb].first; else ans[i + 1] += a[i + 1] - a[i] - sg[lb].second + sg[lb].first; } } for (int i = 0; i < n; ++i) cout << ans[i] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...