Submission #508927

#	Time	Username	Problem	Language	Result	Execution time	Memory
508927		ITO	Snowball (JOI21_ho_t2)	C++11	100 / 100	238 ms	13916 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll lr[200001][2];
priority_queue<pair<ll, ll>> pq;
int main() {
    int n, q;
    ll x, xt, w, cu = 0, ml = 0, mr = 0;
    cin >> n >> q;
    cin >> xt;
    for (int i = 1; i < n; i++) {
        cin >> x;
        pq.push(make_pair(xt - x, i));
        xt = x;
    }
    for (int i = 0; i < q; i++) {
        cin >> w;
        cu += w;
        if (cu < ml) {
            ml = cu;
            while (!pq.empty() && -pq.top().first <= mr - ml) {
                lr[pq.top().second][0] = -pq.top().first - mr;
                lr[pq.top().second - 1][1] = mr;
                pq.pop();
            }
        }
        if (cu > mr) {
            mr = cu;
            while (!pq.empty() && -pq.top().first < mr - ml) {
                lr[pq.top().second][0] = -ml;
                lr[pq.top().second - 1][1] = ml - pq.top().first;
                pq.pop();
            }
        }
    }
    while (!pq.empty()) {
        lr[pq.top().second][0] = -ml;
        lr[pq.top().second - 1][1] = mr;
        pq.pop();
    }
    lr[0][0] = -ml;
    lr[n - 1][1] = mr;
    for (int i = 0; i < n; i++) {
        cout << lr[i][0] + lr[i][1] << '\n';
    }
    return 0;
}

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