Submission #541314

#	Time	Username	Problem	Language	Result	Execution time	Memory
541314		NyanCatTW1	Snowball (JOI21_ho_t2)	C++17	100 / 100	88 ms	12280 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    cin >> N >> Q;

    vector<pair<LL, int> > ballDists;
    LL last;
    for (int i = 0; i < N; i++) {
        LL cur;
        cin >> cur;
        if (i) {
            ballDists.push_back(make_pair(cur - last, i));
        }

        last = cur;
    }

    sort(ballDists.begin(), ballDists.end(), greater<pair<LL, int> >());

    vector<LL> winds;
    LL curPos = 0, maxPos = 0, minPos = 0;

    vector<LL> ans(N);
    for (int i = 0; i < Q; i++) {
        LL cur;
        cin >> cur;

        curPos += cur;
        LL newMaxPos = max(maxPos, curPos);
        LL newMinPos = min(minPos, curPos);

        while (ballDists.size() && ballDists.back().first <= newMaxPos - newMinPos) {
            auto gap = ballDists.back();
            ballDists.pop_back();

            ans[gap.second] -= minPos;
            ans[gap.second - 1] += maxPos;

            LL intersectArea = gap.first - (maxPos - minPos);
            if (cur > 0) ans[gap.second - 1] += intersectArea;
            else ans[gap.second] += intersectArea;
        }

        maxPos = newMaxPos;
        minPos = newMinPos;
    }

    ans[0] -= minPos;
    ans[N - 1] += maxPos;

    for (auto gap : ballDists) {
        ans[gap.second] -= minPos;
        ans[gap.second - 1] += maxPos;
    }

    for (int i = 0; i < N; i++) {
        cout << ans[i] << '\n';
    }
}

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