Submission #444490

#TimeUsernameProblemLanguageResultExecution timeMemory
444490paliloSnowball (JOI21_ho_t2)C++17
100 / 100
138 ms9528 KiB
#include <bits/stdc++.h> using namespace std; template <class T> bool chmin(T& _old, T _new) { return _old > _new && (_old = _new, true); } template <class T> bool chmax(T& _old, T _new) { return _old < _new && (_old = _new, true); } #ifdef palilo template <typename C, typename T = decay_t<decltype(*begin(declval<C>()))>, typename enable_if<!is_same<C, string>::value>::type* = nullptr> ostream& operator<<(ostream& os, const C& container) { stringstream ss; ss << '['; bool first = true; for (const auto& x : container) { if (!first) ss << ", "; first = false; ss << x; } ss << ']'; return os << ss.str(); } template <typename T1, typename T2> ostream& operator<<(ostream& os, const pair<T1, T2>& p) { stringstream ss; ss << '(' << p.first << ", " << p.second << ')'; return os << ss.str(); } template <typename T> void debug_msg(string name, T arg) { cerr << name << " = " << arg << endl; } template <typename T1, typename... T2> void debug_msg(string names, T1 arg, T2... args) { cerr << names.substr(0, names.find(',')) << " = " << arg << " | "; debug_msg(names.substr(names.find(',') + 2), args...); } #define debug(...) cerr << '(' << __LINE__ << ')' << ' ', debug_msg(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) #endif int main() { cin.tie(nullptr)->sync_with_stdio(false); #ifdef palilo freopen("in", "r", stdin); freopen("out", "w", stdout); #endif int n, q; cin >> n >> q; vector<int64_t> a(n), w(q); for (auto& x : a) { cin >> x; } for (auto& x : w) { cin >> x; } partial_sum(w.begin(), w.end(), w.begin()); debug(w); vector<int64_t> d; for (int i = 0, j; i != q;) { if (w[i] == 0) { ++i; continue; } const bool lhs = w[i] < 0; auto farthest = w[i]; for (j = i + 1; j != q; ++j) { if (lhs) { if (w[j] > 0) { break; } chmin(farthest, w[j]); } else { if (w[j] < 0) { break; } chmax(farthest, w[j]); } } debug(d, farthest); i = j; if (!d.empty() && (d.back() < 0) == lhs) { if (lhs) { chmin(d.back(), farthest); } else { chmax(d.back(), farthest); } continue; } if (d.size() > 1 && (d.end()[-2] < 0) == lhs && abs(d.end()[-2]) >= abs(farthest)) { continue; } d.emplace_back(farthest); } if (d.empty()) { for (int i = 0; i < n; ++i) { cout << "0\n"; } return 0; } if (d.size() == 1) { const bool lhs = d.front() < 0; const auto snow = abs(d.front()); if (lhs) { cout << snow << '\n'; } for (int i = 0; i < n - 1; ++i) { cout << min(snow, a[i + 1] - a[i]) << '\n'; } if (!lhs) { cout << snow; } return 0; } auto binary = [&](int64_t val) { int lo = 0, hi = d.size() - 2; while (lo != hi) { const int mid = (lo + hi) >> 1; abs(d[mid]) + abs(d[mid + 1]) < val ? lo = mid + 1 : hi = mid; } return lo; }; debug(d); vector<int64_t> ans(n); ans.front() -= min(d.end()[-2], d.end()[-1]); ans.back() += max(d.end()[-2], d.end()[-1]); for (int i = 0; i < n - 1; ++i) { auto gap = a[i + 1] - a[i]; const auto it = binary(gap); if (d[it] < 0) { auto snow = min(gap, -d[it]); ans[i + 1] += snow, gap -= snow; ans[i] += min(gap, d[it + 1]); } else { auto snow = min(gap, d[it]); ans[i] += snow, gap -= snow; ans[i + 1] += min(gap, -d[it + 1]); } } for (const auto& x : ans) { cout << x << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...