Submission #920397

#	Time	Username	Problem	Language	Result	Execution time	Memory
920397		borisAngelov	Snowball (JOI21_ho_t2)	C++17	100 / 100	81 ms	17084 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;

int n, m;

long long a[maxn];
long long b[maxn];

long long maxDeltaL[maxn];
long long maxDeltaR[maxn];

long long maxLeft[maxn];
long long maxRight[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= m; ++i)
    {
        cin >> b[i];
    }

    long long currDelta = 0;

    for (int i = 1; i <= m; ++i)
    {
        currDelta += b[i];
        maxDeltaL[i] = min(maxDeltaL[i - 1], currDelta);
        maxDeltaR[i] = max(maxDeltaR[i - 1], currDelta);
    }

    maxLeft[1] = a[1] + maxDeltaL[m];
    maxRight[n] = a[n] + maxDeltaR[m];

    for (int i = 1; i <= n - 1; ++i)
    {
        // min time to intersect

        int l = 1;
        int r = m;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (a[i] + maxDeltaR[mid] <= a[i + 1] + maxDeltaL[mid])
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }

        maxRight[i] = a[i] + maxDeltaR[r];
        maxLeft[i + 1] = a[i + 1] + maxDeltaL[r];

        if (l <= m)
        {
            //decides who will get the snow

            if (b[l] < 0)
            {
                maxLeft[i + 1] = maxRight[i];
            }
            else
            {
                maxRight[i] = maxLeft[i + 1];
            }
        }
    }

    for (int i = 1; i <= n; ++i)
    {
        cout << maxRight[i] - maxLeft[i] << "\n";
    }

    return 0;
}

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