Submission #891263

#	Time	Username	Problem	Language	Result	Execution time	Memory
891263		vjudge1	Bitaro's travel (JOI23_travel)	C++17	0 / 100	356 ms	6192 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()
const int N = 120000;


int n;
vector<int> a;


int solve(int l, int r, int x){
	if(l <= 0){
		return abs(a.back() - x);
	}else if(r >= n-1){
		return abs(a[0] - x);
	}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 abs(a[q] - x) + solve(q, r, a[q]);
	}else{
		int q = upper_bound(all(a), x * 2 - a[l-1]) - a.begin() - 1;
		return abs(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 r = upper_bound(all(a), x) - a.begin(), l = r-1;
		if(l < 0){
			cout << abs(a.back() - x);
		}else if(l >= n-1){
			cout << abs(x - a[0]);
		}else if(abs(a[r] - x) >= abs(a[l] - x)){
			cout << abs(a[l] - x) + solve(l, l, x);
		}else{
			cout << abs(a[r] - x) + solve(r, r, x);
		}
		cout << '\n';
	}
	return 0;
}

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