Submission #1208085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208085		PenguinsAreCute	Bitaro's travel (JOI23_travel)	C++17	100 / 100	347 ms	7568 KiB

travel

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 262'144;
struct segr {
	vector<int> val;
	segr(): val(MAXN<<1,0) {}
	void up(int x, int u) {val[x+MAXN] = u;}
	void build() {
		for(int i=MAXN;--i;)
			val[i] = max(val[i<<1],val[i<<1|1]);
	}
	int qry(int x, int t) {
		for(x+=MAXN;x;x>>=1)
			if((x&1) && val[--x] > t) {
				while(x<MAXN)
					x = x << 1 | (val[x<<1|1] > t);
				return x-MAXN;
			}
		return -1;
	}
};
struct segl {
	vector<int> val;
	segl(): val(MAXN<<1,0) {}
	void up(int x, int u) {val[x+MAXN] = u;}
	void build() {
		for(int i=MAXN;--i;)
			val[i] = min(val[i<<1],val[i<<1|1]);
	}
	int qry(int x, int t) {
		for(x+=MAXN;x;x>>=1) {
			if((x&1) && val[x++] <= t) {
				x--;
				while(x<MAXN)
					x = x << 1 | (val[x<<1] > t);
				return x-MAXN;
			}
		}
		return -1;
	}
};
int main() {
	int n;
	cin >> n;
	int x[n];
	for(int i=0;i<n;i++)
		cin >> x[i];
	segr refr;
	refr.up(0,2.1e9);
	for(int i=1;i<n;i++)
		refr.up(i, 2 * x[i] - x[i-1]);
	refr.build();
	segl refl;
	refl.up(n-1,-1.1e9);
	for(int i=0;i<n-1;i++)
		refl.up(i, 2 * x[i] - x[i+1]);
	refl.build();

	int q;
	cin >> q;
	while(q--) {
		int s;
		cin >> s;
		auto it = lower_bound(x,x+n,s);
		int l, r;
		if(it==x||(it!=x+n&&(*it)-s<s-(*(it-1))))
			l = r = it - x;
		else
			l = r = it - x - 1;
		long long ans = abs(x[l] - s);
		while(1) {
			int nwl = refr.qry(l+1,r==n-1?2e9:x[r+1]);
			ans += abs(x[l] - x[nwl]);
			l = nwl;
			if(l == 0 && r == n - 1)
				break;
			ans += abs(x[++r] - x[nwl]);
			int nwr = refl.qry(r,l==0?-1e9:x[l-1]);
			ans += abs(x[r] - x[nwr]);
			r = nwr;
			if(l == 0 && r == n - 1)
				break;
			ans += abs(x[nwr] - x[--l]);
		}
		cout << ans << "\n";
	}
}

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