Submission #1216243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216243		k1r1t0	Bitaro's travel (JOI23_travel)	C++20	100 / 100	308 ms	61348 KiB

travel

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 210000;
const int LOGN = 20;
const int INF = (int)(1e18);

int n, q, x[N], a[N], b[N], p[N], ta[LOGN][N], tb[LOGN][N];

int geta(int l, int r) {
	if (l > r) return -INF;
	int sz = 31 - __builtin_clz(r - l + 1);
	return max(ta[sz][l], ta[sz][r - (1 << sz) + 1]);
}

int getb(int l, int r) {
	if (l > r) return -INF;
	int sz = 31 - __builtin_clz(r - l + 1);
	return max(tb[sz][l], tb[sz][r - (1 << sz) + 1]);
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> x[i];
	x[0] = -(int)(2e9);
	x[n + 1] = (int)(2e9);
	for (int i = 0; i <= n; i++)
		a[i] = b[i] = x[i + 1] - x[i];
	for (int i = 0; i <= n; i++)
		p[i] = (i == 0 ? 0 : p[i - 1]) + a[i];
	for (int i = 1; i <= n; i++)
		a[i] -= p[i - 1];
	for (int i = 0; i <= n; i++)
		b[i] -= p[n] - p[i];
	for (int i = 0; i <= n; i++)
		ta[0][i] = a[i], tb[0][i] = b[i];
	for (int k = 1; k < LOGN; k++)
	for (int i = 0; i + (1 << k) - 1 <= n; i++) {
		ta[k][i] = max(ta[k - 1][i], ta[k - 1][i + (1 << (k - 1))]);
		tb[k][i] = max(tb[k - 1][i], tb[k - 1][i + (1 << (k - 1))]);
	}
	cin >> q;
	while (q--) {
		int s; cin >> s;
		int pos = lower_bound(x + 1, x + 1 + n, s) - x;
		int ans = 0;
		if (x[pos] - s < s - x[pos - 1]) {
			ans += x[pos] - s;
			s = pos;
		} else {
			ans += s - x[pos - 1];
			s = pos - 1;
		}
		int l = s - 1, r = s + 1;
		if (n > 1) {
			bool onr = true;
			if (x[l + 1] - x[l] <= x[r] - x[r - 1]) {
				ans += x[l + 1] - x[l];
				l--;
				onr = false;
			} else {
				ans += x[r] - x[r - 1];
				r++;
			}
			while (1 <= l || r <= n) {
				if (onr) {
					int pos = r - 1;
					int dist = x[r - 1] - x[l];
					int val = dist - p[pos - 1];
					int lb = pos, rb = n;
					while (lb < rb) {
						int mid = (lb + rb) / 2 + 1;
						if (val > geta(pos, mid - 1)) lb = mid;
						else rb = mid - 1;
					}
					ans += x[lb] - x[pos];
					if (l >= 1) {
						ans += x[lb] - x[l];
						l--;
					}
					r = lb + 1;
				} else {
					int pos = l + 1;
					int dist = x[r] - x[l + 1];
					int val = dist - (p[n] - p[pos - 1]);
					int lb = 1, rb = pos;
					while (lb < rb) {
						int mid = (lb + rb) / 2;
						if (val >= getb(mid, pos - 1)) rb = mid;
						else lb = mid + 1;
					}
					ans += x[pos] - x[rb];
					if (r <= n) {
						ans += x[r] - x[rb];
						r++;
					}
					l = rb - 1;
				}
				onr = !onr;
			}
		}
		cout << ans << '\n';
	}
}

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