Submission #850035

#	Time	Username	Problem	Language	Result	Execution time	Memory
850035		IBory	Bitaro's travel (JOI23_travel)	C++17	100 / 100	916 ms	18520 KiB

travel

#include <bits/stdc++.h>
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int SZ = 1 << 18;
ll X[SZ], LR[SZ], RL[SZ], pre[SZ];
// LR[n]: L 방향으로 가는데, 만약 출발 위치가 LR[n] 이하이면 반드시 오른쪽으로 꺾어야 한다

pii Merge(pii& a, pii& b) {
	return { min(a.first, b.first), max(a.second, b.second) };
}

struct Seg {
	pii T[SZ << 1];
	void Build() {
		for (int i = SZ; i > 0; --i) {
			T[i] = Merge(T[i * 2], T[i * 2 + 1]);
		}
	}
	pii Query(int L, int R) {
		pii ret = { 2e9, -2e9 };
		for (L += SZ - 1, R += SZ - 1; L <= R; L >>= 1, R >>= 1) {
			if (L & 1) ret = Merge(ret, T[L++]);
			if (!(R & 1)) ret = Merge(ret, T[R--]);
		}
		return ret;
	}
} T;

int main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int N, Q;
	cin >> N;
	X[0] = -1E18;
	X[N + 1] = 1E18;
	for (int i = 1; i <= N; ++i) cin >> X[i];
	for (int i = 1; i <= N; ++i) {
		if (1 < i) {
			ll d = X[i] - X[i - 1];
			int L = i - 1, R = N + 1;
			while (L + 1 < R) {
				int mid = (L + R) >> 1;
				(X[mid] - X[i] < d ? L : R) = mid;
			}
			LR[i] = L - 1;
		}
		else LR[i] = 1e9;
		if (i < N) {
			ll d = X[i + 1] - X[i];
			int L = 0, R = i + 1;
			while (L + 1 < R) {
				int mid = (L + R) >> 1;
				(X[i] - X[mid] <= d ? R : L) = mid;
			}
			RL[i] = R + 1;
		}
		else RL[i] = -1e9;
		T.T[SZ + i - 1] = { RL[i], LR[i] };
	}
	T.Build();

	for (int i = 1; i <= N; ++i) {
		int L = i, R = i, cur = i, left = -1;
		if (i == N || (i != 1 && X[i] - X[i - 1] <= X[i + 1] - X[i])) left = 1;
		else left = 0;
		while (L != 1 && R != N) {
			if (left) {
				int l = 1, r = cur;
				while (l + 1 < r) {
					int mid = (l + r) >> 1;
					(T.Query(mid, cur - 1).second >= R ? l : r) = mid;
				}
				L = l;
				pre[i] += X[cur] - X[L];
				cur = L;
			}
			else {
				int l = cur, r = N;
				while (l + 1 < r) {
					int mid = (l + r) >> 1;
					(T.Query(cur + 1, mid).first <= L ? r : l) = mid;
				}
				R = r;
				pre[i] += X[R] - X[cur];
				cur = R;
			}
			left ^= 1;
		}
		pre[i] += X[N] - X[1];
	}

	cin >> Q;
	while (Q--) {
		ll P;
		cin >> P;
		auto it = lower_bound(X + 1, X + N + 1, P) - X;
		ll ans = 0, DL = (1 < it ? P - X[it - 1] : 2E9), DR = (it <= N ? X[it] - P : 2E9);
		if (DL <= DR) ans = DL + pre[it - 1];
		else ans = DR + pre[it];
		cout << ans << '\n';
	}

	return 0;
}

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