Submission #1122971

#TimeUsernameProblemLanguageResultExecution timeMemory
1122971osmanaySnowball (JOI21_ho_t2)C++17
0 / 100
0 ms320 KiB
#include <iostream> #include <vector> using namespace std; int main() { int n, q; cin >> n >> q; vector <int> x(n), w(q), mx(q + 1), mn(q + 1); for (int i = 0; i < n; ++i) { cin >> x[i]; } int cur = 0; for (int i = 0; i < q; ++i) { cin >> w[i]; cur += w[i]; mx[i + 1] = max(mx[i], cur); mn[i + 1] = min(mn[i], cur); } vector <int> ans(n); ans.front() -= mn.back(); ans.back() += mx.back(); for (int i = 0; i + 1 < n; ++i) { int d = x[i + 1] - x[i]; if (mx.back() - mn.back() < d) { ans[i] += mx.back(); ans[i + 1] -= mn.back(); } else { int l = 0, r = q; while (l < r - 1) { int m = (l + r) / 2; if (mx[m] - mn[m] < d) { l = m; } else { r = m; } } ans[i] += mx[l]; ans[i + 1] -= mn[l]; int os = d - mx[l] + mn[l]; if (w[l] > 0) { ans[i] += os; } else { ans[i + 1] += os; } } } for (int e : ans) { cout << e << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...