Submission #1137830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137830		denislav	Bitaro's travel (JOI23_travel)	C++20	100 / 100	245 ms	51168 KiB

travel

# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;

const int MAX=2e5+11,LOG=20;

int n,q;
long long a[MAX];

void read()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
}

long long st_left[MAX][LOG];

void prepare_left()
{
    for(int i=2;i<=n;i++) st_left[i][0]=a[i]*2-a[i-1];

    for(int j=1;j<LOG;j++)
    {
        for(int i=2;i<=n;i++)
        {
            if(i-(1<<j)<=0) continue;
            st_left[i][j]=max(st_left[i][j-1],st_left[i-(1<<(j-1))][j-1]);
        }
    }
}

int st_right[MAX][LOG];

void prepare_right()
{
    for(int i=1;i<n;i++) st_right[i][0]=a[i]*2-a[i+1];

    for(int j=1;j<LOG;j++)
    {
        for(int i=1;i<n;i++)
        {
            if(i+(1<<j)>n) continue;
            st_right[i][j]=min(st_right[i][j-1],st_right[i+(1<<(j-1))][j-1]);
        }
    }
}

pair<int,long long> go_left(int l, int r)
{
    if(r==n) return {1,a[l]-a[1]};

    long long ans=0,orig_l=l;
    for(int j=LOG-1;j>=0;j--)
    {
        if(l-(1<<j)>=1 and st_left[l][j]<=a[r+1])
        {
            l-=(1<<j);
        }
    }

    ans+=a[orig_l]-a[l];
    ans+=a[r]-a[l];
    return {l,ans};
}

pair<int,long long> go_right(int l, int r)
{
    if(l==1) {return {n,a[n]-a[r]};}

    long long ans=0,orig_r=r;
    for(int j=LOG-1;j>=0;j--)
    {
        if(r+(1<<j)<=n and st_right[r][j]>a[l-1])
        {
            r+=(1<<j);
        }
    }

    ans+=a[r]-a[orig_r];
    ans+=a[r]-a[l];
    return {r,ans};
}

void solve()
{
    cin>>q;
    while(q--)
    {
        long long ans=0,x;
        cin>>x;

        int start=lower_bound(a+1,a+n+1,x)-a;
        if(start==n+1) {ans=x-a[n];start=n;}
        else if(start==1) {ans=a[1]-x;start=1;}
        else
        {
            if(x-a[start-1]<=a[start]-x) {ans=x-a[start-1];start--;}
            else {ans=a[start]-x;}
        }

        int l=start,r=start;
        int dir=0;
        if(l==1 or (r!=n and a[l]-a[l-1]>a[l+1]-a[l])) dir=1;

        while(!(l==1 and r==n))
        {
            //cout<<"->"<<l<<" "<<r<<" "<<dir<<"\n";

            if(dir==0)
            {
                pair<int,long long> pa=go_left(l,r);
                ans+=pa.second;
                l=pa.first;
            }
            else
            {
                pair<int,long long> pa=go_right(l,r);
                ans+=pa.second;
                r=pa.first;
            }

            dir^=1;
        }

        /*
        int curr=start;
        while(!(l==1 and r==n))
        {
            if(r==n) {ans+=abs(a[curr]-a[l-1]);l--;curr=l;}
            else if(l==1) {ans+=abs(a[curr]-a[r+1]);r++;curr=r;}
            else if(abs(a[curr]-a[l-1])<=abs(a[curr]-a[r+1])) {ans+=abs(a[curr]-a[l-1]);l--;curr=l;}
            else {ans+=abs(a[curr]-a[r+1]);r++;curr=r;}
        }
        */

        cout<<ans<<"\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    read();
    prepare_left();
    prepare_right();
    solve();

    return 0;
}

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