Submission #920655

#	Time	Username	Problem	Language	Result	Execution time	Memory
920655		andrei_iorgulescu	Bitaro's travel (JOI23_travel)	C++14	100 / 100	488 ms	70740 KiB

travel

#include <bits/stdc++.h>

using namespace std;

#define int long long

int n,q;
int a[200005];
int v1[200005],v2[200005];
int lg[200005];
int rmq1[20][200005],rmq2[20][200005];

void build()
{
    for (int i = 2; i <= n; i++)
        lg[i] = 1 + lg[i / 2];
    for (int i = 1; i <= n; i++)
        rmq1[0][i] = v1[i],rmq2[0][i] = v2[i];
    for (int j = 1; j <= lg[n]; j++)
    {
        for (int i = 1; i <= n - (1 << j) + 1; i++)
        {
            rmq1[j][i] = min(rmq1[j - 1][i],rmq1[j - 1][i + (1 << (j - 1))]);
            rmq2[j][i] = max(rmq2[j - 1][i],rmq2[j - 1][i + (1 << (j - 1))]);
        }
    }
}

int query1(int l,int r)
{
    int lgg = lg[r - l + 1];
    return min(rmq1[lgg][l],rmq1[lgg][r - (1 << lgg) + 1]);
}

int query2(int l,int r)
{
    int lgg = lg[r - l + 1];
    return max(rmq2[lgg][l],rmq2[lgg][r - (1 << lgg) + 1]);
}

int moveleft(int &l,int &r)
{
    ///se presupune ca sunt in r
    if (l == 1)
        return 0;
    if (r == n)
    {
        l = 1;
        return a[n] - a[1];
    }
    ///daca a[r + 1] - a[r] < a[r] - a[l - 1], atunci clar nu fac nimic
    if (a[r + 1] - a[r] < a[r] - a[l - 1])
        return 0;
    ///daca pentru fiecare 2 <= y <= l - 1, a[y] - a[y - 1] <= a[r + 1] - a[y], adica 2 * a[y] - a[y - 1] <= a[r + 1], merg pana la 1
    if (query2(2,l - 1) <= a[r + 1])
    {
        l = 1;
        return a[r] - a[1];
    }
    ///altfel vreau sa gasesc cel mai mare y <= l - 1 pentru care v2[y] > a[r + 1]
    int st = 1,pas = 1 << 17;
    while (pas != 0)
    {
        if (st + pas < l and query2(st + pas,l - 1) > a[r + 1])
            st += pas;
        pas /= 2;
    }
    l = st;
    return a[r] - a[l];
}

int moveright(int &l,int &r)
{
    ///se presupune ca sunt in l
    if (r == n)
        return 0;
    if (l == 1)
    {
        r = n;
        return a[n] - a[1];
    }
    ///daca a[r + 1] - a[l] >= a[l] - a[l - 1], nu fac nimic
    if (a[r + 1] - a[l] >= a[l] - a[l - 1])
        return 0;
    ///daca pentru fiecare r + 1 <= y <= n - 1, a[y + 1] - a[y] < a[y] - a[l - 1] <=> a[y + 1] - 2 * a[y] < -a[l - 1] <=> 2 * a[y] - a[y + 1] > a[l - 1], merg pana la final
    if (query1(r + 1,n - 1) > a[l - 1])
    {
        r = n;
        return a[n] - a[l];
    }
    ///altfel vreau sa gasesc y-ul minim >= r + 1 pentru care a[y + 1] - a[y] >= a[y] - a[l - 1] adica v1[y] <= a[l - 1]
    int st = r,pas = 1 << 17;
    while (pas != 0)
    {
        if (st + pas < n and query1(r + 1,st + pas) > a[l - 1])
            st += pas;
        pas /= 2;
    }
    st++;
    r = st;
    return a[r] - a[l];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    a[n + 1] = 1e10;
    a[0] = -1e10;
    for (int i = 1; i <= n; i++)
        v1[i] = 2 * a[i] - a[i + 1];
    for (int i = 1; i <= n; i++)
        v2[i] = 2 * a[i] - a[i - 1];
    build();
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int ans = 0;
        int p;
        cin >> p;
        int l,r;
        int st = 0,pas = 1 << 17;
        while (pas != 0)
        {
            if (st + pas <= n and a[st + pas] <= p)
                st += pas;
            pas /= 2;
        }
        if (st == 0)
            ans = a[1] - p,l = 1,r = 1;
        else if (st == n)
            ans = p - a[n],l = n,r = n;
        else
        {
            if (p - a[st] <= a[st + 1] - p)
                ans = p - a[st],l = st,r = st;
            else
                ans = a[st + 1] - p,l = st + 1,r = st + 1;
        }
        int idx = 0;
        while (l != 1 or r != n)
        {
            idx++;
            if (idx % 2 == 1)
                ans += moveright(l,r);
            else
                ans += moveleft(l,r);
        }
        cout << ans << '\n';
    }
    return 0;
}

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