Submission #1146736

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146736		KhoaDuy	Bitaro's travel (JOI23_travel)	C++17	100 / 100	406 ms	33904 KiB

travel

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> x(n);
    for(int i=0;i<n;i++){
        cin >> x[i];
    }
    int limri[n],limle[n];
    limri[n-1]=0;
    limri[0]=0;
    for(int i=n-2;i>0;i--){
        int low=0,high=i-1;
        low--,high++;
        while(high-low>1){
            int mid=((high-low)>>1)+low;
            if(x[i]-x[mid]<=x[i+1]-x[i]){
                high=mid;
            }
            else{
                low=mid;
            }
        }
        limri[i]=high;
    }
    limle[0]=n-1;
    limle[n-1]=n-1;
    for(int i=1;i<n-1;i++){
        int low=i+1,high=n-1;
        low--,high++;
        while(high-low>1){
            int mid=((high-low)>>1)+low;
            if(x[mid]-x[i]<x[i]-x[i-1]){
                low=mid;
            }
            else{
                high=mid;
            }
        }
        limle[i]=low;
    }
    int sparseri[18][n],sparsele[18][n];
    int loga[n+1];
    loga[1]=0;
    for(int i=2;i<=n;i++){
        loga[i]=loga[i>>1]+1;
    }
    for(int j=0;j<n;j++){
        sparseri[0][j]=limri[j];
        sparsele[0][j]=limle[j];
    }
    for(int i=1;i<18;i++){
        for(int j=0;j+(1<<i)<=n;j++){
            sparsele[i][j]=max(sparsele[i-1][j],sparsele[i-1][j+(1<<(i-1))]);
            sparseri[i][j]=min(sparseri[i-1][j],sparseri[i-1][j+(1<<(i-1))]);
        }
    }
    int q;
    cin >> q;
    while(q--){
        int s;
        cin >> s;
        int le,curr,ri;
        curr=lower_bound(x.begin(),x.end(),s)-x.begin();
        if(curr==x.size()){
            cout << s-x[0] << endl;
            continue;
        }
        else if(curr==0){
            cout << x[n-1]-s << endl;
            continue;
        }
        if(s-x[curr-1]<=x[curr]-s){
            curr--;
        }
        le=curr-1,ri=curr+1;
        long long ans=abs(s-x[curr]);
        while(le>=0||ri<n){
            if(le<0){
                ans+=(x[n-1]-x[curr]);
                break;
            }
            if(ri>=n){
                ans+=(x[curr]-x[0]);
                break;
            }
            if(x[curr]-x[le]<=x[ri]-x[curr]){
                int low=0,high=le;
                low--,high++;
                while(high-low>1){
                    int mid=((high-low)>>1)+low;
                    int l=mid,r=le;
                    if(max(sparsele[loga[r-l+1]][l],sparsele[loga[r-l+1]][r-(1<<loga[r-l+1])+1])>=ri){
                        low=mid;
                    }
                    else{
                        high=mid;
                    }
                }
                ans+=(x[curr]-x[low]);
                curr=low,le=curr-1;
            }
            else{
                int low=ri,high=n-1;
                low--,high++;
                while(high-low>1){
                    int mid=((high-low)>>1)+low;
                    int l=ri,r=mid;
                    if(min(sparseri[loga[r-l+1]][l],sparseri[loga[r-l+1]][r-(1<<loga[r-l+1])+1])<=le){
                        high=mid;
                    }
                    else{
                        low=mid;
                    }
                }
                ans+=(x[high]-x[curr]);
                curr=high,ri=curr+1;
            }
        }
        cout << ans << endl;
    }
}

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