oj.uz

Submission #891269

# Submission time Handle Problem Language Result Execution time Memory
891269 2023-12-22T15:53:24 Z vjudge1 Bitaro's travel (JOI23_travel) C++17
0 / 100
 337 ms 3412 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
int n;
vector<int> a;


int solve(int l, int r, int x){
	if(l <= 0){
		return a[n-1] - x;
	}else if(r >= n-1){
		return x - a[0];
	}else if(abs(a[l-1] - x) <= abs(a[r+1] - x)){
		int q = lower_bound(all(a), x * 2 - a[r+1]) - a.begin();
		return x - a[q] + solve(q, r, a[q]);
	}else{
		int q = upper_bound(all(a), x * 2 - a[l-1]) - a.begin() - 1;
		return a[q] - x + solve(l, q, a[q]);
	}
}


signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	a.resize(n);
	for(auto &e : a) cin >> e;
	int q; cin >> q;
	while(q--){
		int x; cin >> x;
		int pos = upper_bound(all(a), x) - a.begin() - 1;
		if(pos < 0){
			cout << abs(a.back() - x);
		}else if(pos >= n-1){
			cout << abs(x - a[0]);
		}else if(abs(a[pos+1] - x) >= abs(a[pos] - x)){
			cout << abs(a[pos] - x) + solve(pos, pos, x);
		}else{
			cout << abs(a[pos+1] - x) + solve(pos+1, pos+1, x);
		}
		cout << '\n';
	}
	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 400 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 337 ms 3412 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

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