제출 #1247392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1247392		raphaeltfa	Bitaro's travel (JOI23_travel)	C++20	100 / 100	488 ms	4196 KiB

travel

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int inf = 1e18;
int n;
vector<int> arr;

void preprocess(){
    cin >> n;; 
    arr.resize(n + 2);
    arr[0] = -inf, arr[n + 1] = inf;
    for(int i = 0; i < n; i++) cin >> arr[i + 1];
} 

int jump(int l, int mid, int r){
    if(l == 0) return arr[n] - mid;
    if(r == n + 1) return mid - arr[1];
    if(mid - arr[l] > arr[r] - mid){
        int x = upper_bound(arr.begin(), arr.end(), 2 * mid - arr[l]) - arr.begin() - 1;
        return arr[x] - mid + jump(l, arr[x], x + 1);
    } else {
        int x = lower_bound(arr.begin(), arr.end(), 2 * mid - arr[r]) - arr.begin();
        return mid - arr[x] + jump(x - 1, arr[x], r);
    }
}

void solve(){
    int pos, l, r; cin >> pos;
    r = upper_bound(arr.begin(), arr.end(), pos) - arr.begin();
    l = r - 1;
    cout << jump(l, pos, r) << endl;


}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); 
    preprocess();
    int test; cin >> test;
    while(test--) solve();
}

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