Submission #1235446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235446		AlgorithmWarrior	Bitaro's travel (JOI23_travel)	C++20	100 / 100	322 ms	35496 KiB

travel

#include <bits/stdc++.h>

using namespace std;

int const NMAX=200005;
int const LOG=20;
int n;
int x[NMAX];

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

int rmax[NMAX][LOG];
int rmin[NMAX][LOG];
int logr[NMAX];

void precalc_rmq(){
    int i,j;
    for(i=1;i<=n;++i){
        if(2<=i)
            rmax[i][0]=2*x[i]-x[i-1];
        if(i<=n-1)
            rmin[i][0]=2*x[i]-x[i+1];
    }
    for(j=1;j<LOG;++j)
        for(i=1;i<=n-(1<<j)+1;++i){
            rmax[i][j]=max(rmax[i][j-1],rmax[i+(1<<(j-1))][j-1]);
            rmin[i][j]=min(rmin[i][j-1],rmin[i+(1<<(j-1))][j-1]);
        }
    for(i=2;i<NMAX;++i)
        logr[i]=logr[i/2]+1;
}

int range_max(int l,int r){
    int lg=logr[r-l+1];
    return max(rmax[l][lg],rmax[r-(1<<lg)+1][lg]);
}

int range_min(int l,int r){
    int lg=logr[r-l+1];
    return min(rmin[l][lg],rmin[r-(1<<lg)+1][lg]);
}

void drive_left(int& l,int& r,long long& dist);
void drive_right(int& l,int& r,long long& dist);

void drive_left(int& l,int& r,long long& dist){
    if(r==n){
        dist+=x[l]-x[1];
        l=1;
        return;
    }
    if(l==2 || range_max(2,l-1)<=x[r+1]){
        dist+=x[l]-x[1];
        l=1;
        dist+=x[r]-x[l];
        drive_right(l,r,dist);
        return;
    }
    /// [)
    int st=2,dr=l;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(range_max(mij,l-1)>x[r+1])
            st=mij;
        else
            dr=mij;
    }
    dist+=x[l]-x[st];
    l=st;
    dist+=x[r]-x[l];
    drive_right(l,r,dist);
}

void drive_right(int& l,int& r,long long& dist){
    if(l==1){
        dist+=x[n]-x[r];
        r=n;
        return;
    }
    if(r==n-1 || range_min(r+1,n-1)>x[l-1]){
        dist+=x[n]-x[r];
        r=n;
        dist+=x[r]-x[l];
        drive_left(l,r,dist);
        return;
    }
    /// (]
    int st=r,dr=n-1;
    while(dr-st>1){
        int mij=(st+dr)/2;
        if(range_min(r+1,mij)<=x[l-1])
            dr=mij;
        else
            st=mij;
    }
    dist+=x[dr]-x[r];
    r=dr;
    dist+=x[r]-x[l];
    drive_left(l,r,dist);
}

void process_queries(){
    int q;
    cin>>q;
    while(q--){
        int qx;
        cin>>qx;
        if(qx<=x[1]){
            long long dist=x[1]-qx;
            int l=1,r=1;
            drive_right(l,r,dist);
            cout<<dist<<'\n';
            continue;
        }
        if(x[n]<=qx){
            long long dist=qx-x[n];
            int l=n,r=n;
            drive_left(l,r,dist);
            cout<<dist<<'\n';
            continue;
        }
        int id=upper_bound(x+1,x+n+1,qx)-x;
        if(qx-x[id-1]<=x[id]-qx)
            --id;
        long long dist=abs(qx-x[id]);
        int l=id,r=id;
        if(id==1)
            drive_right(l,r,dist);
        else
            if(id==n)
                drive_left(l,r,dist);
            else
                if(x[id]-x[id-1]<=x[id+1]-x[id])
                    drive_left(l,r,dist);
                else
                    drive_right(l,r,dist);
        cout<<dist<<'\n';
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read();
    precalc_rmq();
    process_queries();
    return 0;
}

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