Submission #1296401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1296401		Icelast	Bitaro's travel (JOI23_travel)	C++20	100 / 100	635 ms	4704 KiB

travel

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 2*1e5+5, INF = 4e18+9;
void solve(){
    int n;
    cin >> n;
    vector<ll> a(n+2);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    a[0] = -INF, a[n+1] = INF;
    int Q;
    cin >> Q;
    for(int i = 1; i <= Q; i++){
        ll s;
        cin >> s;
        if(n == 1){
            cout << abs(s - a[1]) << "\n";
            continue;
        }
        if(s <= a[1]){
            cout << a[n] - s << "\n";
            continue;
        }
        if(s >= a[n]){
            cout << s - a[1] << "\n";
            continue;
        }
        int l = upper_bound(a.begin(), a.end(), s) - a.begin() - 1, r = l+1;
        int dir = 0;
        ll ans = 0;
        while(l != 0 || r != n+1){
            if(l == 0){
                ans += a[n] - s;
                r = n+1;
                continue;
            }
            if(r == n+1){
                ans += s - a[1];
                l = 0;
                continue;
            }

            if(dir == 0){
                //s - a[j] <= a[r] - s
                //a[j] >= 2s - a[r]
                int j = lower_bound(a.begin(), a.end(), s*2 - a[r]) - a.begin();
                dir ^= 1;
                if(j > l) continue;
                ans += s - a[j];
                s = a[j];
                l = j-1;
            }else{
                //s - a[l] > a[j] - s
                //a[j] < 2s - a[l]
                int j = lower_bound(a.begin(), a.end(), s*2 - a[l]) - a.begin() - 1;
                dir ^= 1;
                if(j < r) continue;
                ans += a[j] - s;
                s = a[j];
                r = j+1;

            }
        }
        cout << ans << "\n";
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}

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