Submission #1122341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122341		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<int> X(N + 1);

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

    vector<int> W(Q + 1);
    vector<int> 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];
    }

    vector<int> 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 (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