Submission #967548

#	Time	Username	Problem	Language	Result	Execution time	Memory
967548		josanneo22	Bitaro's travel (JOI23_travel)	C++17	100 / 100	446 ms	8100 KiB

travel

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

const int nax = 200005;
int N, Q;
i64 X[nax];

void solve(int p) {
	int l = 0, r = N + 1, res = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (X[mid] <= p) res = mid, l = mid + 1;
		else r = mid - 1;
	}
	int L = res;
	l = 0, r = N + 1, res = -1;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (X[mid] > p) res = mid, r = mid - 1;
		else l = mid + 1;
	}
	int R = res;
	i64 ans = 0, cur = p;
	// cout << "first : " << L << ' ' << R << ' ' << ans << '\n';
	if (abs(cur - X[L]) <= abs(X[R] - cur)) {
		ans += abs(cur - X[L]);
		cur = X[L];
		L -= 1;
	}
	else {
		ans += abs(cur - X[R]);
		cur = X[R];
		R += 1;
	}
	// cout << "second : " << L << ' ' << R << ' ' << ans << '\n';
	while (L >= 1 && R <= N) {
		// cout << L << ' ' << R << ' ' << ans << ' ' << cur << '\n';
		// cout << abs(cur - X[L]) << ' ' << abs(X[R] - cur) << '\n';
		if (abs(cur - X[L]) <= abs(X[R] - cur)) {
			i64 dis = abs(X[R] - cur);
			l = 0, r = N + 1, res = -1;
			while (l <= r) {
				int mid = (l + r) >> 1;
				if (X[mid] >= cur - dis) {
					res = mid;
					r = mid - 1;
				}
				else l = mid + 1;
			}
			if (res == 0) res = 1;
			ans += abs(cur - X[res]);
			cur = X[res];
			L = res - 1;
		}
		else {
			i64 dis = abs(X[L] - cur);
			l = 0, r = N + 1, res = -1;
			while (l <= r) {
				int mid = (l + r) >> 1;
				if (X[mid] <= cur + dis) {
					res = mid;
					l = mid + 1;
				}
				else r = mid - 1;
			}
			if (res == N + 1) res = N;
			ans += abs(cur - X[res]);
			cur = X[res];
			R = res + 1;
		}
		if (L == 0 || R == N + 1) break;
	}
	ans += abs(cur - X[1]);
	ans += abs(cur - X[N]);
	cout << ans << '\n';
	return;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	cin >> N;
	for (int i = 1; i <= N; i++) cin >> X[i];
	X[0] = -1E18; X[N + 1] = 1E18;
	cin >> Q;
	while (Q--) {
		int o; cin >> o;
		solve(o);
	}
}

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