Submission #1122963

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122963		osmanay	Snowball (JOI21_ho_t2)	C++17	0 / 100	4 ms	328 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 == 1)
        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++)
        {
            long long len = X[i + 1] - X[i];

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

            //maximum sum < len
            int j = lower_bound(bestSum.begin(), bestSum.end(), len) - bestSum.begin();
            if (bestSum[j] > len)
                j--;

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

            //remaining snow between two points. It will be taken in the next wind.
            int diff = len - (maxL[j] - minR[j]);

            if (W[j + 1] > 0)   //next wind blows to the east. point[i] will take the remaining snow
                res[i] += diff;
            else                //point[i] will take the remaining snow
                res[i + 1] += diff;
        }

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

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