Submission #951759

#	Time	Username	Problem	Language	Result	Execution time	Memory
951759		Lobo	Bitaro's travel (JOI23_travel)	C++17	100 / 100	483 ms	13980 KiB

travel

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int maxn = 2e5+10;
const int inf = 2e9+10;

int n, a[maxn], tr1[4*maxn], tr2[4*maxn];

void build1(int no, int l, int r) {
	if(l == r) {
		if(l == n) tr1[no] = -inf;
		else tr1[no] = 2*a[l]-a[l+1];
		return;
	}
	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	build1(lc,l,mid);
	build1(rc,mid+1,r);
	tr1[no] = min(tr1[lc],tr1[rc]);
}
int cnt = 0;

// leftmost i with i >= pos and x[i] <= val
int find1(int no, int l, int r, int pos, int val) {assert(++cnt <= 70);
	if(tr1[no] > val || r < pos) return -1;
	if(l == r) {
		return l;
	}

	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;

	if(l >= pos) {
		if(tr1[lc] <= val) return find1(lc,l,mid,pos,val);
		return find1(rc,mid+1,r,pos,val);
	}

	int ansl = find1(lc,l,mid,pos,val);
	if(ansl != -1) return ansl;
	return find1(rc,mid+1,r,pos,val);
}

void build2(int no, int l, int r) {
	if(l == r) {
		if(l == 1) tr2[no] = inf;
		else tr2[no] = 2*a[l]-a[l-1];
		return;
	}
	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	build2(lc,l,mid);
	build2(rc,mid+1,r);
	tr2[no] = max(tr2[lc],tr2[rc]);
}
// rightmost i with i <= pos and x[i] >= val
int find2(int no, int l, int r, int pos, int val) {assert(++cnt <= 70);
	if(tr2[no] < val || l > pos) return -1;
	if(l == r) {
		return l;
	}

	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	if(r <= pos) {
		if(tr2[rc] >= val) return find2(rc,mid+1,r,pos,val);
		return find2(lc,l,mid,pos,val);
	}

	int ansr = find2(rc,mid+1,r,pos,val);
	if(ansr != -1) return ansr;
	return find2(lc,l,mid,pos,val);
}

int32_t main() {
	// freopen("in.in","r",stdin);

	cin >> n;

	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}

	build1(1,1,n);
	build2(1,1,n);
	int q; cin >> q;
	// assert(q == 1);
	while(q--) {
		int l = -1,r, sd = 0;
		int p; cin >> p;
		long long ans = 0;

		int l1 = 0;
		int r1 = n;
		int ansbs = -1;
		while(l1 <= r1) {
			int mid = (l1+r1)/2;

			if(mid == n || a[mid+1] >= p) {
				ansbs = mid;
				r1 = mid-1;
			}
			else {
				l1 = mid+1;
			}
		}

		if(ansbs != 0 && (ansbs == n || p-a[ansbs] <= a[ansbs+1] - p)) {
			ans+= p-a[ansbs];
			l = ansbs;
			r = ansbs;
		}
		else {
			ans+= a[ansbs+1]-p;
			l = ansbs+1;
			r = ansbs+1;
		}
		
		int qtalt = 0;
		while(l != 1 || r != n) {
			if(sd == 0) {
				if(l == 1) {
					ans+= a[n]-a[l];
					r = n;
					sd = 1;
					qtalt++;
				}
				else if(r == n) {
					ans+= a[l]-a[1];
					l = 1;
					qtalt++;
				}
				else if(a[l]-a[l-1] <= a[r+1]-a[l]) {
					cnt = 0;
					int ansb = find2(1,1,n,l-1,a[r+1]+1);
					assert(cnt <= 70);
					ans+= a[l]-a[ansb];
					l = ansb;
					qtalt++;
				}
				else {
					cnt = 0;
					int ansb = find1(1,1,n,r+1,a[l-1]);
					assert(cnt <= 70);
					ans+= a[ansb]-a[l];
					r = ansb;
					sd = 1;
					qtalt++;
				}
			}
			else {
				if(l == 1) {
					ans+= a[n]-a[r];
					r = n;
					qtalt++;
				}
				else if(r == n) {
					ans+= a[r]-a[1];
					sd = 0;
					l = 1;
					qtalt++;
				}
				else if(a[r]-a[l-1] <= a[r+1]-a[r]) {
					cnt = 0;
					int ansb = find2(1,1,n,l-1,a[r+1]+1);
					assert(cnt <= 70);
					ans+= a[r]-a[ansb];
					sd = 0;
					l = ansb;
					qtalt++;
				}
				else {
					cnt = 0;
					int ansb = find1(1,1,n,r+1,a[l-1]);
					assert(cnt <= 70);
					ans+= a[ansb]-a[r];
					r = ansb;
					qtalt++;
				}
			}
		}
		assert(qtalt <= 20);
		cout << ans << endl;
	}
}

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