Submission #891271

#	Time	Username	Problem	Language	Result	Execution time	Memory
891271		vjudge1	Bitaro's travel (JOI23_travel)	C++17	100 / 100	426 ms	8236 KiB

travel

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
int n;
vector<int> a;



int solve(int l, int r, int x){
	if(l <= 0){
		return a[n-1] - x;
	}else if(r >= n-1){
		return x - a[0];
	}else if(abs(a[l-1] - x) <= abs(a[r+1] - x)){
		int q = lower_bound(all(a), x * 2 - a[r+1]) - a.begin();
		return x - a[q] + solve(q, r, a[q]);
	}else{
		int q = upper_bound(all(a), x * 2 - a[l-1]) - a.begin() - 1;
		return a[q] - x + solve(l, q, a[q]);
	}
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	a.resize(n);
	for(auto &e : a) cin >> e;
	int q; cin >> q;
	while(q--){
		int x; cin >> x;
		int pos = upper_bound(all(a), x) - a.begin() - 1;
		if(pos < 0){
			cout << abs(a.back() - x);
		}else if(pos >= n-1){
			cout << abs(x - a[0]);
		}else if(abs(a[pos+1] - x) >= abs(a[pos] - x)){
			cout << abs(a[pos] - x) + solve(pos, pos, a[pos]);
		}else{
			cout << abs(a[pos+1] - x) + solve(pos+1, pos+1, a[pos+1]);
		}
		cout << '\n';
	}
	return 0;
}

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