Submission #936915

#	Time	Username	Problem	Language	Result	Execution time	Memory
936915		emanIaicepsa	Snowball (JOI21_ho_t2)	C++14	100 / 100	110 ms	15428 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);
template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int N, Q;
    cin >> N >> Q;
    vector<ll> arr(N + 2), ansR(N + 2), ansL(N + 2);
    arr[0] = -1e18, arr[N + 1] = 1e18;
    for (int i = 1; i <= N; i++) cin >> arr[i];

    vector<pair<ll, int>> difL, difR;
    for (int i = 1; i <= N; i++) {
        difL.push_back({arr[i - 1] - arr[i], i});
        difR.push_back({arr[i + 1] - arr[i], i});
    }

    sort(difL.begin(), difL.end(), greater<pair<ll, int>>());
    sort(difR.begin(), difR.end());
    
    vector<ll> ope(Q);
    for (auto &i: ope) cin >> i;
    
    ll maxR = 0, minL = 0, cur = 0;

    int ridx = 0, lidx = 0;

    for (int i = 0; i < Q; i++) {
        cur += ope[i];

        if (cur > maxR) {
            while (ridx < N && difR[ridx].first + minL < cur) {
                ansR[difR[ridx].second] += maxR;
                ansR[difR[ridx].second] += max(0LL, difR[ridx].first + minL - maxR);
                ridx++;
            }
            maxR = cur;
        }

        if (cur < minL) {
            while (lidx < N && difL[lidx].first + maxR > cur) {
                ansL[difL[lidx].second] -= minL;
                ansL[difL[lidx].second] -= min(0LL, difL[lidx].first + maxR - minL);
                lidx++;
            }
            minL = cur;
        }
    }

    while (ridx < N) {
        ansR[difR[ridx].second] += maxR;
        ridx++;
    }

    while (lidx < N) {
        ansL[difL[lidx].second] -= minL;
        lidx++;
    }

    for (int i = 1; i <= N; i++) {
        // dbg(i, ansL[i], ansR[i]);
        cout << ansL[i] + ansR[i] << '\n';
    }


}

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