Submission #1122359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122359		osmanay	Snowball (JOI21_ho_t2)	C++14	0 / 100	1 ms	336 KiB

Main

//Snowball, OJ. Intervals problem.
//Osman Ay, November 2024.

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

using namespace std;

int main()
{
    int N, Q;
    cin >> N >> Q;

    vector<long long> X(N + 1);

    for (int i = 1; i <= N; i++)
        cin >> X[i];

    vector<long long> W(Q + 1);
    vector<long long> preSum(Q + 1, 0), bestSum(Q+1, 0), maxL(Q + 1, 0), minR(Q + 1, 0);

    for(int i=1; i<=Q; i++)
    {
        cin >> W[i];

        preSum[i] = preSum[i - 1] + W[i];

        maxL[i] = max(maxL[i-1], preSum[i]);

        
        minR[i] = min(minR[i-1], preSum[i]);


        bestSum[i] = maxL[i] - minR[i];
    }

    if (N == 0)
        cout << maxL[Q] - minR[Q] << endl;
    else
    {

        vector<long long> res(N + 1, 0);
        res[1] = -minR[Q];
        res[N] = maxL[Q];

        for (int i = 1; i <= N - 1; i++)
        {
            int len = X[i + 1] - X[i];

            if (len >= maxL[Q] - minR[Q])
            {
                res[i] += maxL[Q];
                res[i + 1] += -minR[Q];
                continue;
            }

            int j = upper_bound(bestSum.begin(), bestSum.end(), len) - bestSum.begin();
            j--;

            res[i] += maxL[j];
            res[i + 1] += -minR[j];

            int diff = len - (maxL[j] - minR[j]);

            if (j < N && diff > 0)
            {
                if (W[j + 1] > 0)
                    res[i] += diff;
                else
                    res[i + 1] += diff;
            }
        }

        for (int i = 1; i <= N; i++)
            cout << res[i] << endl;
    }
}

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