oj.uz

Submission #1030650

# Submission time Handle Problem Language Result Execution time Memory
1030650 2024-07-22T08:08:13 Z Unforgettablepl Bitaro's travel (JOI23_travel) C++17
0 / 100
 4 ms 8632 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long

struct segtree{
	vector<int> tree;
	segtree():tree(524288){}
	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 = 0;
		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] = -2e9;
	arr[n+1] = 2e9;
	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();
		} else {
			above--;
			ans+=(*above)-curr_pos;
			curr_l=curr_r=above-arr.begin();	
		}
		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 left
				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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Incorrect 4 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Incorrect 4 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8536 KB Output is correct
2 Correct 4 ms 8632 KB Output is correct
3 Correct 3 ms 8472 KB Output is correct
4 Correct 3 ms 8540 KB Output is correct
5 Incorrect 3 ms 8540 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8540 KB Output is correct
2 Incorrect 4 ms 8540 KB Output isn't correct
3 Halted 0 ms 0 KB -