Submission #1328292

#	Time	Username	Problem	Language	Result	Execution time	Memory
1328292		bearrbearr	Bitaro's travel (JOI23_travel)	C++20	100 / 100	577 ms	4296 KiB

travel

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair<int,int>
#define fir first
#define sec second
#define pb push_back

vector<int>x;
int mana(int idx){
    return lower_bound(x.begin(),x.end(),idx)-x.begin();
}

signed main(){
    int n; cin>>n;
    x.pb(-1e15);

    for(int q=1;q<=n;q++){
        int apa; cin>>apa;
        x.pb(apa);
    }
    
    int qu; cin>>qu;
    while(qu--){
        int idx; cin>>idx;
        int l,r;
        l=r=mana(idx);
        if(l>n)l=r=n;

        int ans=0;
        if(l>1){
            if(idx-x[l-1]<=x[l]-idx){
                l--,r--;
            }
        }
    //    cout<<idx<<endl;
        ans+=abs(x[l]-idx); idx=x[l];

        while(true){
            if(l==1 || r==n){
                ans+=x[n]-x[1]; break;
            }
         //   cout<<l<<" "<<r<<endl;

            if(idx-x[l-1]<=x[r+1]-idx){
                int hmm=mana(2*idx-x[r+1]);
                ans+=idx-x[hmm];
                idx=x[hmm];
                l=hmm;
            }
            else{
                int hmm=mana(2*idx-x[l-1])-1;
                ans+=x[hmm]-idx;
                idx=x[hmm];
                r=hmm;
            }

        }

        cout<<ans<<endl;
    }
}

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