Submission #1280878

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280878		tvgk	Bitaro's travel (JOI23_travel)	C++20	5 / 100	18 ms	4008 KiB

travel

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const int mxN = 1e5 + 7, inf = 1e9 + 7;

int n, lt[mxN * 4], rt[mxN * 4], a[mxN];

void Build(int j = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        lt[j] = 2 * a[l] - a[l - 1];
        rt[j] = 2 * a[l] - a[l + 1];
        return;
    }

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
    lt[j] = max(lt[j * 2], lt[j * 2 + 1]);
    rt[j] = min(rt[j * 2], rt[j * 2 + 1]);
}

void RWalk(int u, int vt, int& res, int j = 1, int l = 1, int r = n)
{
    if (r < vt || res)
        return;

    if (vt <= l && a[u] < rt[j])
        return;

    if (l == r)
    {
        res = l;
        return;
    }

    int mid = (l + r) / 2;
    RWalk(u, vt, res, j * 2, l, mid);
    RWalk(u, vt, res, j * 2 + 1, mid + 1, r);
}

void LWalk(int v, int vt, int& res, int j = 1, int l = 1, int r = n)
{
    if (vt < l || res)
        return;

    if (r <= vt && lt[j] <= a[v])
        return;

    if (l == r)
    {
        res = l;
        return;
    }

    int mid = (l + r) / 2;
    LWalk(v, vt, res, j * 2 + 1, mid + 1, r);
    LWalk(v, vt, res, j * 2, l, mid);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie();
    cout.tie();
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    a[0] = -inf;
    a[n + 1] = 2 * inf;
    Build();

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int vt;
        cin >> vt;

        ll ans = 0;
        int v = lower_bound(a, a + n + 2, vt) - a;
        int u = v - 1;
        if (a[v] - vt < vt - a[u])
        {
            ans += a[v] - vt;
            vt = v++;
        }
        else
        {
            ans += vt - a[u];
            vt = u--;
        }

        while (1 <= u || v <= n)
        {
            if (v - vt == 1)
            {
                int res = 0;
                RWalk(u, vt, res);
                if (!res)
                    res = n;

                ans += a[res] - a[vt];
                if (u)
                {
                    ans += a[res] - a[u];
                    vt = u;
                    u--;
                }
                v = res + 1;
            }
            else
            {
                int res = 0;
                LWalk(v, vt, res);
                if (res == 0)
                    res = 1;

                ans += a[vt] - a[res];
                if (v <= n)
                {
                    ans += a[v] - a[res];
                    vt = v;
                    v++;
                }
                u = res - 1;
            }
        }
        cout << ans << '\n';
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 30
• Subtask 4: 0 / 55