Submission #1006703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006703		snpmrnhlol	Bitaro's travel (JOI23_travel)	C++17	100 / 100	672 ms	7252 KiB

travel

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5;
int v[N];
int n;
int lb(int nr){
    int l = 0,r = n;
    while(l != r){
        int mij = (l + r)/2;
        if(v[mij] >= nr)r = mij;
        else l = mij + 1;
    }
    return l;
}
int main(){
    cin>>n;
    for(int i = 0;i < n;i++){
        cin>>v[i];
    }
    int q;
    cin>>q;
    for(int i = 0;i < q;i++){
        int x;
        cin>>x;
        ll ans = 0;
        int l,r,pos;
        int tmp;
        tmp = lb(x);
        if(tmp != 0 && (tmp == n || x - v[tmp - 1] <= v[tmp] - x)){
            ans+=x - v[tmp - 1];
            l = tmp - 1;r = tmp - 1;
        }else{
            ans+=v[tmp] - x;
            l = tmp;r = tmp;
        }
        pos = 0;
        while(l != 0 || r != n - 1){
            if(l == 0 || r == n - 1){
                ///go to n - 1
                ans+=v[n - 1] - v[0];
                l = 0;
                r = n - 1;
                continue;
            }
            if(pos == 0){
                tmp = lb(v[l] - (v[r + 1] - v[l]));
                if(tmp == l){
                    ///bad go to r + 1
                    pos = 1;
                    ans+=v[r + 1] - v[l];
                    r++;
                }else{
                    pos = 0;
                    ans+=v[l] - v[tmp];
                    l = tmp;
                }
            }else{
                tmp = lb(v[r] + (v[r] - v[l - 1])) - 1;
                if(tmp == r){
                    pos = 0;
                    ans+=v[r] - v[l - 1];
                    l--;
                }else{
                    pos = 1;
                    ans+=v[tmp] - v[r];
                    r = tmp;
                }
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

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