Submission #967546

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
967546	2024-04-22T12:10:04 Z	josanneo22	Bitaro's travel (JOI23_travel)	C++17	0 / 100	1 ms	600 KB

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

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	420 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	600 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Incorrect	0 ms	344 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #2

0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	420 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	600 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Incorrect	0 ms	344 KB	Output isn't correct
13	Halted	0 ms	0 KB	-

Subtask #3

0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Incorrect	0 ms	348 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #4

0 / 55.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	420 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	600 KB	Output is correct
11	Correct	1 ms	348 KB	Output is correct
12	Incorrect	0 ms	344 KB	Output isn't correct
13	Halted	0 ms	0 KB	-