Submission #700895

#	Time	Username	Problem	Language	Result	Execution time	Memory
700895		bebra	Snowball (JOI21_ho_t2)	C++17	100 / 100	195 ms	23252 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

#define dbg(x) cerr << #x << ": " << x << endl;



int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<ll> a(n);
    for (auto& x : a) {
        cin >> x;
    }

    ll max_value = 0;
    ll min_value = 0;

    ll curr_value = 0;
    vector<ll> ans(n);
    set<pair<ll, int>> distances;
    for (int i = 0; i < n - 1; ++i) {
        distances.emplace(a[i + 1] - a[i], i);
    }
    ll left_add = 0;
    ll right_add = 0;
    while (q--) {
        ll w;
        cin >> w;
        curr_value += w;
        if (w > 0) {
            if (curr_value <= max_value) continue;
            
            ll d = curr_value - max_value;
            max_value = max(max_value, curr_value);

            ans[n - 1] += d;
            while (!distances.empty()) {
                auto [value, idx] = *distances.begin();
                if (value - left_add - right_add > d) break;
                ans[idx] += left_add + value - left_add - right_add;
                ans[idx + 1] += right_add;
                distances.erase(*distances.begin());
            }
            left_add += d;
        } else {
            if (curr_value >= min_value) continue;

            ll d = min_value - curr_value;
            min_value = min(min_value, curr_value);

            ans[0] += d;
            while (!distances.empty()) {
                auto [value, idx] = *distances.begin();
                if (value - left_add - right_add > d) break;
                ans[idx + 1] += right_add + value - left_add - right_add;
                ans[idx] += left_add;
                distances.erase(*distances.begin());
            }
            right_add += d;
        }
    }

    for (const auto& [value, idx] : distances) {
        ans[idx] += left_add;
        ans[idx + 1] += right_add;
    }

    for (auto x : ans) {
        cout << x << '\n';
    }

    return 0;
}

• Subtask 1: 33 / 33
• Subtask 2: 67 / 67