Submission #757734

#	Time	Username	Problem	Language	Result	Execution time	Memory
757734		happypotato	Bitaro's travel (JOI23_travel)	C++17	100 / 100	634 ms	5828 KiB

travel

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
#define pb push_back
// global
const int mxN = 2e5 + 1;
int ans[mxN];
vector<int> v;
int n;
void init() {
	// init

}
void FindAnswer(int pos) {
	if (pos == 0 || pos == n - 1) {
		ans[pos] = v[n - 1] - v[0];
		return;
	}
	int lb = pos, rb = pos;
	ans[pos] = 0;
	int cur, dist;
	bool toleft;
	if (v[pos] - v[pos - 1] <= v[pos + 1] - v[pos]) {
		ans[pos] += v[pos] - v[pos - 1];
		cur = v[pos - 1];
		lb = pos - 1; rb = pos;
		toleft = true;
	} else {
		ans[pos] += v[pos + 1] - v[pos];
		cur = v[pos + 1];
		lb = pos; rb = pos + 1;
		toleft = false;
	}
	int lpos, rpos;
	// cerr << "ANSWER " << pos << endl;
	while (0 < lb && rb < n - 1) {
		// cerr << "STATE " << lb << ' ' << rb << ' ' << ans[pos] << endl;
		dist = v[rb] - v[lb];
		if (toleft) {
			lpos = lower_bound(v.begin(), v.end(), cur - dist) - v.begin();
			if (lpos != lb) {
				ans[pos] += cur - v[lpos];
				cur = v[lpos];
				lb = lpos;
				continue;
			}
		} else {
			rpos = upper_bound(v.begin(), v.end(), cur + dist) - v.begin() - 1;
			if (rpos != rb) {
				ans[pos] += v[rpos] - cur;
				cur = v[rpos];
				rb = rpos;
				continue;
			}
		}
		if (cur - v[lb - 1] <= v[rb + 1] - cur) {
			ans[pos] += cur - v[lb - 1];
			cur = v[lb - 1];
			lb--;
			toleft = true;
		} else {
			ans[pos] += v[rb + 1] - cur;
			cur = v[rb + 1];
			rb++;
			toleft = false;
		}
	}
	// cerr << "FINAL STATE " << lb << ' ' << rb << ' ' << ans[pos] << endl;
	if (lb == 0) {
		ans[pos] += v[n - 1] - cur;
	} else if (rb == n - 1) {
		ans[pos] += cur - v[0];
	}
	// cerr << "FINAL ANSWER " << pos << ": " << ans[pos] << endl;
	return;
}
void solve() {
	// solve
	cin >> n;
	v.resize(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	for (int i = 0; i < n; i++) {
		FindAnswer(i);
	}
	int q;
	cin >> q;
	while (q--) {
		int x;
		cin >> x;
		int pos = lower_bound(v.begin(), v.end(), x) - v.begin();
		if (pos == 0) {
			cout << (v[0] - x) + ans[0] << endl;
		} else if (pos == n) {
			cout << (x - v[pos - 1]) + ans[pos - 1] << endl;
		} else {
			// between v[pos - 1] and v[pos]
			if ((x - v[pos - 1]) <= (v[pos] - x)) {
				cout << (x - v[pos - 1]) + ans[pos - 1] << endl;
			} else {
				cout << (v[pos] - x) + ans[pos] << endl;
			}
		}
	}
}
int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	init(); solve();
}

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