Submission #826703

#	Time	Username	Problem	Language	Result	Execution time	Memory
826703		Asymmetry	Bitaro's travel (JOI23_travel)	C++17	100 / 100	282 ms	74576 KiB

travel

#include<bits/stdc++.h>
using namespace std;
using LL=long long;
#define FOR(i,l,r) for(int i=(l);i<=(r);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) int(x.size())
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#ifdef DEBUG
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector t(n + 2, 0ll);
	FOR (i, 1, n)
		cin >> t[i];
	const LL INF = LL(1e18);
	t[0] = -INF;
	t[n + 1] = INF;
	debug(t);
	const int Z = __lg(int(1e9)) + 2;
	debug(Z);
	vector type(n + 1, Z - 1);
	REP (i, n + 1) {
		REP (j, Z)
			if ((1ll << j) > (t[i + 1] - t[i])) {
				type[i] = j;
				break;
			}
	}
	debug(type);
	vector prv(n + 1, vector(Z, 0));
	auto nxt = prv;
	REP (i, Z)
		prv[1][i] = 1;
	FOR (i, 2, n) {
		prv[i] = prv[i - 1];
		REP (j, Z)
			if ((1 << j) <= t[i] - t[i - 1])
				prv[i][j] = i;
	}

	REP (i, Z)
		nxt[n][i] = n;
	for (int i = n - 1; i >= 1; --i) {
		nxt[i] = nxt[i + 1];
		REP (j, Z)
			if ((1 << j) <= t[i + 1] - t[i])
				nxt[i][j] = i;
	}

	debug(prv);
	debug(nxt);

	int q;
	cin >> q;
	REP (xd, q) {
		LL x;
		cin >> x;
		LL ans = 0;
		int pos = int(upper_bound(t.begin(), t.end(), x) - t.begin());
		if (t[pos] - x >= x - t[pos - 1])
			--pos;
		ans = abs(x - t[pos]);
		int lf = pos, rg = pos;
		debug(pos, t[pos] - t[pos - 1], t[pos + 1] - t[pos]);
		int side = (t[pos] - t[pos - 1]) <= (t[pos + 1] - t[pos]);
		int pot = 0;
		while (lf != 1 || rg != n) {
			debug(lf, rg, side);
			while ((2 << pot) <= t[rg] - t[lf])
				++pot;
			debug(pot);
			if (side) {
				// left
				ans += t[lf] - t[prv[lf][pot]];
				lf = prv[lf][pot];
				if (lf > 1 && t[lf] - t[lf - 1] <= t[rg + 1] - t[lf]) {
					ans += t[lf] - t[lf - 1];
					--lf;
				}
				else if (rg < n) {
					ans += t[rg] - t[lf];
					side ^= 1;
				}
			}
			else {
				// right
				ans += t[nxt[rg][pot]] - t[rg];
				rg = nxt[rg][pot];
				if (rg < n && t[rg + 1] - t[rg] < t[rg] - t[lf - 1]) {
					ans += t[rg + 1] - t[rg];
					++rg;
				}
				else if (lf > 1) {
					ans += t[rg] - t[lf];
					side ^= 1;
				}
			}
		}
		cout << ans << '\n';
	}
}

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