oj.uz

Submission #1064771

# Submission time Handle Problem Language Result Execution time Memory
1064771 2024-08-18T17:36:34 Z GusterGoose27 Bitaro's travel (JOI23_travel) C++17
0 / 100
 43 ms 63324 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 2e5+5;
const int B = 18;
const int inf = 1e9+5;
int n;
vector<int> arr;
int ddiff[2][MAXN][B];
ll ans[MAXN];

ll sim(int l, int r, bool side, int b_prev = B) {
	if (r >= n) {
		assert(!side);
		return arr[l]-arr[0];
	}
	if (l < 0) {
		assert(side);
		return arr[n-1]-arr[r];
	}
	if (side) {
		for (int i = b_prev-1; i >= 0; i--) {
			int nxt = min(n-1, r+(1<<i));
			if (ddiff[0][r][i] < -arr[l]) return sim(l, nxt, 1, i)+(arr[nxt]-arr[r]);
		}
		return sim(l, r+1, 0)+arr[r]-arr[l];
	}
	else {
		for (int i = b_prev-1; i >= 0; i--) {
			int nxt = max(0, l-(1<<i));
			if (ddiff[1][l][i] <= arr[r]) return sim(nxt, r, 0, i)+(arr[l]-arr[nxt]);
		}
		return sim(l-1, r, 1)+arr[r]-arr[l];
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	arr.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < n-1; i++) {
		ddiff[0][i][0] = arr[i+1]-2*arr[i];
		ddiff[1][i+1][0] = 2*arr[i+1]-arr[i];
	}
	ddiff[0][n-1][0] = inf;
	ddiff[1][0][0] = inf;
	for (int b = 1; b < B; b++) {
		for (int i = 0; i < n; i++) {
			if (i+(1<<(b-1)) >= n) ddiff[0][i][b] = ddiff[0][i][b-1];
			else ddiff[0][i][b] = max(ddiff[0][i][b-1], ddiff[0][i+(1<<(b-1))][b-1]);
			if (i-(1<<(b-1)) < 0) ddiff[1][i][b] = ddiff[1][i][b-1];
			else ddiff[1][i][b] = max(ddiff[1][i][n-1], ddiff[1][i-(1<<(b-1))][b-1]);
		}
	}
	// sim(3,3,0);
	for (int i = 0; i < n; i++) {
		ans[i] = sim(i, i+1, 0);
	}
	int q; cin >> q;
	for (int i = 0; i < q; i++) {
		int x; cin >> x;
		if (x >= arr[n-1]) {
			cout << (x-arr[n-1]+ans[n-1]) << '\n';
		}
		else {
			int nxt = upper_bound(arr.begin(), arr.end(), x)-arr.begin();
			if (nxt == 0) cout << (arr[0]-x + ans[0]) << '\n';
			else cout << (x-arr[nxt-1] <= arr[nxt]-x ? x-arr[nxt-1]+ans[nxt-1] : arr[nxt]-x+ans[nxt]) << '\n';
		}
	}
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 0 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Runtime error 43 ms 63324 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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