Submission #870022

#	Time	Username	Problem	Language	Result	Execution time	Memory
870022		Megumin2006	Snowball (JOI21_ho_t2)	C++14	100 / 100	90 ms	16664 KiB

Main

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int inf = 4e18;

void solve() {
    int n, q;
    cin >> n >> q;

    vector<int> a(n + 2);
    a[0] = -inf;
    a[n + 1] = inf;
    for(int i = 1; i <= n; ++i) cin >> a[i];

    priority_queue< array<int, 3>, vector< array<int, 3> >, greater< array<int, 3> > > interval;
    for(int i = 0; i <= n; ++i) {
        interval.push({a[i + 1] - a[i], i, i + 1});
    }

    int cur = 0, MaxL = 0, MaxR = 0;
    vector<int> ans(n + 2);
    for(int i = 1; i <= q; ++i) {
        int w;
        cin >> w;
        cur += w;

        MaxR = max(MaxR, cur);
        MaxL = min(MaxL, cur);

        while(1) {
            array<int, 3> fetch = interval.top();
            if (fetch[0] > MaxR - MaxL) break;

            interval.pop();
            int id1 = fetch[1], id2 = fetch[2];
            if (cur > 0) {
                ans[id1] += fetch[0] - abs(MaxL);
                ans[id2] += abs(MaxL);
            }
            else {
                ans[id1] += MaxR;
                ans[id2] += fetch[0] - MaxR;
            }
        }
    }

    while(interval.size()) {
        array<int, 3> fetch = interval.top();
        interval.pop();
        int id1 = fetch[1], id2 = fetch[2];

        ans[id1] += MaxR;
        ans[id2] += abs(MaxL);
    }

    for(int i = 1; i <= n; ++i) {
//        if (ansR[i] == -1) ansR[ fetch[1] ] = max(lastR, fetch[0] - MaxL);
        cout << ans[i] << '\n';
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("cf.inp", "r")) {
        freopen("cf.inp", "r", stdin);
    }
    solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:68:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |         freopen("cf.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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