Submission #919686

#	Time	Username	Problem	Language	Result	Execution time	Memory
919686		boris_mihov	Snowball (JOI21_ho_t2)	C++17	100 / 100	87 ms	16980 KiB

Main

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const int INF  = 1e9;

int n, m;
llong a[MAXN];
llong b[MAXN];
llong min[MAXN];
llong max[MAXN];
llong l[MAXN];
llong r[MAXN];

void solve()
{
    llong sum = 0;
    for (int i = 1 ; i <= m ; ++i)
    {
        sum += b[i];
        min[i] = std::min(min[i - 1], sum);
        max[i] = std::max(max[i - 1], sum);
    }

    l[1] = a[1] + min[m];
    r[n] = a[n] + max[m];

    for (int i = 1 ; i < n ; ++i)
    {
        int ll = 0, rr = m + 1, mid;
        while (ll < rr - 1)
        {
            mid = (ll + rr) / 2;
            if (a[i] + max[mid] <= a[i + 1] + min[mid]) ll = mid;
            else rr = mid;
        }

        r[i] = a[i] + max[ll];
        l[i + 1] = a[i + 1] + min[ll];
        if (rr <= m)
        {
            if (b[rr] < 0) l[i + 1] = r[i];
            else r[i] = l[i + 1];
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        std::cout << r[i] - l[i] << '\n';
    }
}

void input()
{
    std::cin >> n >> m;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }

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

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

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