oj.uz

Submission #891263

# Submission time Handle Problem Language Result Execution time Memory
891263 2023-12-22T15:46:28 Z vjudge1 Bitaro's travel (JOI23_travel) C++17
0 / 100
 356 ms 6192 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()
const int N = 120000;


int n;
vector<int> a;


int solve(int l, int r, int x){
	if(l <= 0){
		return abs(a.back() - x);
	}else if(r >= n-1){
		return abs(a[0] - x);
	}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 abs(a[q] - x) + solve(q, r, a[q]);
	}else{
		int q = upper_bound(all(a), x * 2 - a[l-1]) - a.begin() - 1;
		return abs(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 r = upper_bound(all(a), x) - a.begin(), l = r-1;
		if(l < 0){
			cout << abs(a.back() - x);
		}else if(l >= n-1){
			cout << abs(x - a[0]);
		}else if(abs(a[r] - x) >= abs(a[l] - x)){
			cout << abs(a[l] - x) + solve(l, l, x);
		}else{
			cout << abs(a[r] - x) + solve(r, r, x);
		}
		cout << '\n';
	}
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 764 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 348 KB Output is correct
2 Incorrect 1 ms 764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 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 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Incorrect 356 ms 6192 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 348 KB Output is correct
2 Incorrect 1 ms 764 KB Output isn't correct
3 Halted 0 ms 0 KB -