Submission #1208971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208971		dima2101	Snowball (JOI21_ho_t2)	C++20	100 / 100	182 ms	16144 KiB

Main

#include <bits/stdc++.h>
#define int long long

signed main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n, q;
    std::cin >> n >> q;
    std::vector<int> x(n);
    std::vector<std::pair<int, int>> delta_s(n - 1);
    for (int i = 0; i < n; i++)
    {
        std::cin >> x[i];
    }
    for (int i = 0; i < n - 1; i++)
    {
        delta_s[i].first = x[i + 1] - x[i];
        delta_s[i].second = i;
    }
    std::vector<int> w(q);
    for (int i = 0; i < q; i++)
    {
        std::cin >> w[i];
    }
    std::vector<int> left(n);
    std::vector<int> right(n);
    std::vector<int> pref_min(q, 0);
    std::vector<int> pref_max(q, 0);
    std::vector<int> pref(q, 0);
    pref[0] = w[0];
    for (int i = 1; i < q; i++)
    {
        pref[i] = pref[i - 1] + w[i];
    }
    for (int i = 0; i < q; i++)
    {
        if (i == 0)
        {
            pref_min[i] = std::min(pref_min[i], pref[i]);
            pref_max[i] = std::max(pref_max[i], pref[i]);
        }
        else
        {
            pref_min[i] = std::min(pref_min[i - 1], pref[i]);
            pref_max[i] = std::max(pref_max[i - 1], pref[i]);
        }
    }
    std::sort(delta_s.begin(), delta_s.end());
    int l = 0;
    for (int i = 0; i < q; i++)
    {
        while (l < n - 1 && pref_max[i] - pref_min[i] >= delta_s[l].first)
        {
            // std::cout << l << ' ' << pref_max[i] << ' ' << pref_min[i] << ' ' << delta_s[i].second << std::endl;
            if (i == 0)
            {
                if (pref_max[i] != 0)
                {
                    right[delta_s[l].second] = delta_s[l].first;
                }
                else
                {
                    left[delta_s[l].second + 1] = delta_s[l].first;
                }
            }
            else
            {
                if (pref_max[i] != pref_max[i - 1])
                {
                    right[delta_s[l].second] = pref_max[i - 1] + (delta_s[l].first - pref_max[i - 1] + pref_min[i]);
                    left[delta_s[l].second + 1] = -pref_min[i];
                }
                else
                {
                    left[delta_s[l].second + 1] = delta_s[l].first - pref_max[i];
                    right[delta_s[l].second] = pref_max[i];
                }
            }
            l++;
        }
    }

    for (l; l < n - 1; l++)
    {
        right[delta_s[l].second] = pref_max.back();
        left[delta_s[l].second + 1] = -pref_min.back();
    }
    left[0] = -pref_min.back();
    right.back() = pref_max.back();
    for (int i = 0; i < n; i++)
    {
        std::cout << left[i] + right[i] << std::endl;
    }
}

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