Submission #1064786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064786		GusterGoose27	Bitaro's travel (JOI23_travel)	C++17	100 / 100	139 ms	37028 KiB

travel

#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][b-1], ddiff[1][i-(1<<(b-1))][b-1]);
		}
	}
	sim(4,5,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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55