oj.uz

Submission #850028

# Submission time Handle Problem Language Result Execution time Memory
850028 2023-09-15T16:19:58 Z IBory Bitaro's travel (JOI23_travel) C++17
0 / 100
 326 ms 16048 KB 
#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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 4 ms 8688 KB Output is correct
3 Correct 4 ms 8888 KB Output is correct
4 Incorrect 3 ms 8796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 4 ms 8688 KB Output is correct
3 Correct 4 ms 8888 KB Output is correct
4 Incorrect 3 ms 8796 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 2 ms 8668 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 2 ms 8828 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8796 KB Output is correct
7 Correct 326 ms 15956 KB Output is correct
8 Incorrect 321 ms 16048 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 4 ms 8688 KB Output is correct
3 Correct 4 ms 8888 KB Output is correct
4 Incorrect 3 ms 8796 KB Output isn't correct
5 Halted 0 ms 0 KB -