Submission #602198

#	Time	Username	Problem	Language	Result	Execution time	Memory
602198		SamAnd	Snowball (JOI21_ho_t2)	C++17	100 / 100	133 ms	9836 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 200005;

int n, q;
ll x[N];
ll w[N];

ll p[N];
ll maxu[N], minu[N];

void solv()
{
    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
        cin >> x[i];
    for (int i = 1; i <= q; ++i)
        cin >> w[i];

    for (int i = 1; i <= q; ++i)
        p[i] = p[i - 1] + w[i];
    for (int i = 1; i <= q; ++i)
    {
        minu[i] = min(minu[i - 1], p[i]);
        maxu[i] = max(maxu[i - 1], p[i]);
    }

    for (int i = 1; i <= n; ++i)
    {
        ll ans = 0;
        if (i == 1)
        {
            ans -= minu[q];
        }
        else
        {
            int l = 1, r = q;
            int u = 0;
            while (l <= r)
            {
                int m = (l + r) / 2;
                if (maxu[m] - minu[m] <= x[i] - x[i - 1])
                {
                    u = m;
                    l = m + 1;
                }
                else
                    r = m - 1;
            }

            int m = u;
            if (m == q || p[m + 1] > 0)
            {
                ans -= minu[m];
            }
            else
            {
                ans += (x[i] - x[i - 1] - maxu[m]);
            }
        }

        if (i == n)
        {
            ans += maxu[q];
        }
        else
        {
            int l = 1, r = q;
            int u = 0;
            while (l <= r)
            {
                int m = (l + r) / 2;
                if (maxu[m] - minu[m] <= x[i + 1] - x[i])
                {
                    u = m;
                    l = m + 1;
                }
                else
                    r = m - 1;
            }

            int m = u;
            if (m == q || p[m + 1] < 0)
            {
                ans += maxu[m];
            }
            else
            {
                ans += (x[i + 1] - x[i] + minu[m]);
            }
        }
        cout << ans << "\n";
    }
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    ios_base::sync_with_stdio(false), cin.tie(0);

    int tt = 1;
    //cin >> tt;
    while (tt--)
    {
        solv();
    }
    return 0;
}

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