Submission #957878

#	Time	Username	Problem	Language	Result	Execution time	Memory
957878		peterandvoi	Snowball (JOI21_ho_t2)	C++17	100 / 100	80 ms	14268 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = (int) 2e5 + 5;
const long long INF = (long long) 1e18;

int n, q;
long long a[N], res[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    #ifdef ngu
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
    #endif
    cin >> n >> q;
    a[0] = -INF;
    a[n + 1] = INF;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    vector<pair<long long, int>> delta;
    for (int i = 0; i <= n; ++i) {
        delta.emplace_back(a[i + 1] - a[i], i);
    }
    sort(delta.rbegin(), delta.rend());
    long long cur = 0, L = 0, R = 0;
    for (int i = 1; i <= q; ++i) {
        long long x;
        cin >> x;
        cur += x;
        if (x > 0) {
            R = max(R, cur);
            while (delta.size() && delta.back().first <= L + R) {
                auto [v, id] = delta.back();
                res[id] += v - L;
                res[id + 1] += L;
                delta.pop_back();
            }
        } else {
            L = max(L, -cur);
            while (delta.size() && delta.back().first <= L + R) {
                auto [v, id] = delta.back();
                res[id] += R;
                res[id + 1] += v - R;
                delta.pop_back();
            }
        }
    }
    while (delta.size()) {
        auto [v, id] = delta.back();
        res[id] += R;
        res[id + 1] += L;
        delta.pop_back();
    }
    for (int i = 1; i <= n; ++i) {
        cout << res[i] << "\n";
    }
}

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