Submission #850933

#	Time	Username	Problem	Language	Result	Execution time	Memory
850933		raphaelp	Snowball (JOI21_ho_t2)	C++14	100 / 100	172 ms	15444 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long N, Q;
    cin >> N >> Q;
    vector<long long> X(N);
    for (long long i = 0; i < N; i++)
    {
        cin >> X[i];
    }
    vector<long long> l(N, -1);
    vector<long long> r(N, -1);
    vector<pair<long long, long long>> dist(N - 1);
    for (long long i = 0; i < N - 1; i++)
    {
        dist[i] = {abs(X[i + 1] - X[i]), i};
    }
    sort(dist.begin(), dist.end());
    long long rm = 0, lm = 0, cur = 0, buff = 0;
    for (long long i = 0; i < Q; i++)
    {
        long long val;
        cin >> val;
        cur += val;
        rm = max(rm, cur);
        lm = min(lm, cur);
        while (buff < N - 1 && rm - lm >= dist[buff].first)
        {
            if (val > 0)
            {
                l[dist[buff].second + 1] = -lm;
                r[dist[buff].second] = dist[buff].first + lm;
            }
            else
            {
                r[dist[buff].second] = rm;
                l[dist[buff].second + 1] = dist[buff].first - rm;
            }
            buff++;
        }
    }
    for (long long i = 0; i < N; i++)
    {
        if (l[i] == -1)
            l[i] = -lm;
        if (r[i] == -1)
            r[i] = rm;
        cout << l[i] + r[i] << '\n';
    }
}

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