Submission #1265162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265162		happyboy	Snowball (JOI21_ho_t2)	C++20	100 / 100	139 ms	11288 KiB

Main

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    for (auto& i : a) cin >> i;
    vector<pair<long long, int>> v(n - 1);
    for (int i = 0; i + 1 < n; i++) {
        auto& [d, idx] = v[i];
        d = a[i + 1] - a[i];
        idx = i;
    }
    sort(v.begin(), v.end());
    vector<long long> w(q);
    for (auto& i : w) cin >> i;
    int pt = 0;
    long long curr = 0, mn = 0, mx = 0;
    vector<long long> l(n, -1000000000000000000), r(n, -1000000000000000000);
    //for (auto [d, idx] : v) cout << d << " " << idx << "\n";
    for (auto i : w) {
        curr += i;
        mx = max(mx, curr); mn = min(mn, curr);
        //cout << curr << ": ";
        while (pt + 1 < n && v[pt].first <= mx - mn) {
            int tmp = v[pt].second;
            r[tmp] = l[tmp + 1] = (curr > 0 ? a[tmp + 1] + mn : a[tmp] + mx);
            //cout << r[tmp] << " " << l[tmp + 1] << "\n";
            pt++;
        }
        //cout << "\n";
    }
    //cout << "\n";
    for (int i = 0; i < n; i++) {
        if (l[i] == -1000000000000000000) l[i] = a[i] + mn;
        if (r[i] == -1000000000000000000) r[i] = a[i] + mx;
        //cout << l[i] << " " << r[i] << "\n";
        cout << r[i] - l[i] << "\n";
    }
}

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