Submission #1124222

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124222		E_rK	Snowball (JOI21_ho_t2)	C++17	100 / 100	386 ms	11384 KiB

Main

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

#define debug(x) for(auto& a: x) cout << a << " "
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>  bestSum(Q + 1, 0), maxL(Q + 1, 0), minR(Q + 1, 0);
    long long preSum = 0;
    for (int i = 1; i <= Q; i++)
    {
        cin >> W[i];

        preSum += W[i];

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

        bestSum[i] = maxL[i] - minR[i];
    }
    // debug(bestSum);
    // cout << endl;
    if (N == 1)
        cout << bestSum[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 >= bestSum[Q])
            {
                res[i] += maxL[Q];
                res[i + 1] += -minR[Q];
                continue;
            }

            //len < maximum sum and bestSum[j] > len
            int j = lower_bound(bestSum.begin(), bestSum.end(), len) - bestSum.begin();
            if (bestSum[j] >= len)
                j--;
            // cout<<"j: " << j << endl;
            res[i] += maxL[j];
            res[i + 1] += -minR[j];

            //remaining snow between two points. It will be taken in the next wind.
            long long 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: 33 / 33
• Subtask 2: 67 / 67