#include <bits/stdc++.h>
using namespace std;
int msb[200001];
int getMax(int l, int r, vector<vector<int>>& dp){
int k = msb[r - l + 1];
return max(dp[k][r], dp[k][l + (1 << k) - 1]);
}
int getMin(int l, int r, vector<vector<int>>& dp){
int k = msb[r - l + 1];
return min(dp[k][r], dp[k][l + (1 << k) - 1]);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n;
vector<int> X(n);
for(auto &i : X) cin >> i;
vector<vector<int>> goLeft(20, vector<int> (n, 2e9+1));
vector<vector<int>> goRight(20, vector<int> (n, -2e9-1));
for(int k = 0; k < 20; k++){
for(int i = 0; i < n; i++){
if(k == 0){
if(i == 0 || i == n - 1) continue;
goLeft[k][i] = 2 * X[i] - X[i-1];
goRight[k][i] = 2 * X[i] - X[i+1];
}else{
if(i - (1 << (k-1)) < 0){
goLeft[k][i] = goLeft[k-1][i];
goRight[k][i] = goRight[k-1][i];
}else{
goLeft[k][i] = max(goLeft[k-1][i], goLeft[k-1][i-(1<<(k-1))]);
goRight[k][i] = min(goRight[k-1][i], goRight[k-1][i-(1<<(k-1))]);
}
}
}
}
int currExp = 1;
int exp = -1;
for(int i = 1; i <= n; i++){
if(i == currExp){
exp++;
currExp *= 2;
}
msb[i] = exp;
}
int q; cin >> q;
while(q--){
int x; cin >> x;
int lo = 0;
int hi = n - 1;
int bst = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(X[mid] >= x){
bst = mid;
hi = mid - 1;
}else lo = mid + 1;
}
long long dist = 0;
if(bst == -1){
dist = X[0] - x;
x = 0;
}else if(bst == n-1){
dist = x - X[n-1];
x = n - 1;
}else{
if(x - X[bst] <= X[bst+1]-x){
dist = x - X[bst];
x = bst;
}else{
dist = X[bst+1] - x;
x = bst + 1;
}
}
int l = x, r = x;
while(l != 0 && r != n - 1){
if(X[x] - X[l - 1] <= X[r+1] - X[x]){
lo = 0;
hi = l - 1;
bst = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(getMax(mid, l - 1, goLeft) > X[r+1]){
bst = mid;
lo = mid + 1;
}else hi = mid - 1;
}
dist += X[x] - X[bst];
l = bst;
x = bst;
}else{
lo = r+1;
hi = n - 1;
bst = -1;
while(lo <= hi){
int mid = (lo + hi) / 2;
if(X[l-1] >= getMin(r+1, mid, goRight)){
bst = mid;
hi = mid - 1;
}else lo = mid + 1;
}
dist += X[bst] - X[x];
r = bst;
x = bst;
}
}
dist += X[n-1] - X[0];
cout << dist << "\n";
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Incorrect |
1 ms |
600 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |