Submission #1030660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1030660		Unforgettablepl	Bitaro's travel (JOI23_travel)	C++17	100 / 100	401 ms	16244 KiB

travel

#include <bits/stdc++.h>
using namespace std;

#define int long long

struct segtree{
	vector<int> tree;
	segtree():tree(524288,INT64_MIN){}
	void update(int k,int x){
		k+=262144;
		tree[k]=x;
		while(k/=2){
			tree[k]=max(tree[2*k],tree[2*k+1]);
		}
	}
	int get(int a,int b){
		a+=262144;b+=262144;
		int ans = INT64_MIN;
		while(a<=b){
			if(a&1)ans=max(ans,tree[a++]);
			if(b%2 == 0)ans=max(ans,tree[b--]);
			a/=2;b/=2;
		}
		return ans;
	}
};

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<int> arr(n+2);
	for(int i=1;i<=n;i++)cin>>arr[i];
	arr[0] = -1e12;
	arr[n+1] = 1e12;
	segtree seg;
	for(int i=1;i<=n+1;i++){
		seg.update(i,2ll*arr[i]-arr[i-1]);
	}
	segtree seg2;
	for(int i=0;i<=n;i++){
		seg2.update(i,-(2ll*arr[i]-arr[i+1]));
	}
	int q;
	cin >> q;
	for(int i=1;i<=q;i++){
		int curr_l,curr_r,curr_pos;
		cin >> curr_pos;
		int ans = 0;
		auto above = upper_bound(arr.begin(),arr.end(),curr_pos);
		if((*above)-curr_pos<curr_pos-(*(above-1))){
			ans+=(*above)-curr_pos;
			curr_l=curr_r=above-arr.begin();
			curr_pos=arr[curr_l];
		} else {
			above--;
			ans+=curr_pos-(*above);
			curr_l=curr_r=above-arr.begin();	
			curr_pos=arr[curr_l];
		}
		while(1<curr_l or curr_r<n){
			if(curr_pos-arr[curr_l-1]<=arr[curr_r+1]-curr_pos){
				// We go left
				for(int jump=131072;jump;jump/=2){
					if(curr_l-jump<=0)continue;
					if(seg.get(curr_l-jump+1,curr_l)<=arr[curr_r+1])curr_l-=jump;
				}
				ans+=curr_pos-arr[curr_l];
				curr_pos = arr[curr_l];
			} else {
				// We go right
				for(int jump=131072;jump;jump/=2){
					if(curr_r+jump>n)continue;
					if((-seg2.get(curr_r,curr_r+jump-1))>arr[curr_l-1])curr_r+=jump;
				}
				ans+=arr[curr_r]-curr_pos;
				curr_pos = arr[curr_r];
			}
		}
		cout << ans << '\n';
	}
}

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