#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 1e18;
const int N = 2e5 + 10;
template<typename T>
struct SparseTable {
int len;
vector<vector<T>> st;
T (*F) (T, T);
void init(vector<T> &a, T (*f)(T, T)) {
len = (int)a.size();
F = f;
int mxpw = 32 - __builtin_clz(len);
st.resize(mxpw);
st[0] = a;
for(int k = 1; k < mxpw; k++) {
st[k].resize(len - (1 << k));
for(int i = 0; i < (int)st[k].size(); i++)
st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
}
}
T get(int l, int r) {
assert(l >= 0 && r < len);
int mxpw = 31 - __builtin_clz(r - l + 1);
return F(st[mxpw][l], st[mxpw][r - (1 << mxpw) + 1]);
}
};
SparseTable<ll> st_ld, st_rd;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int n;
cin >> n;
vector<ll> x(n + 2);
x[0] = -INF; x[n + 1] = INF;
for(int i = 1; i <= n; i++)
cin >> x[i];
vector<ll> b(n + 1);
for(int i = 1; i <= n; i++)
b[i] = 2 * x[i + 1] - x[i];
st_ld.init(b, [](ll a, ll b) {return (a > b ? a : b);});
for(int i = 1; i <= n; i++)
b[i] = x[i] - 2 * x[i - 1];
st_rd.init(b, [](ll a, ll b) {return (a > b ? a : b);});
int q;
cin >> q;
while(q --> 0) {
int st;
cin >> st;
if(st <= x[1] || st >= x[n]) {
cout << x[n] - x[1] << '\n';
continue;
}
int lb, rb, bin_lb, bin_rb;
bool turn = 0;
bin_lb = 0, bin_rb = n + 1;
while(bin_rb - bin_lb > 1) {
int mid = (bin_rb + bin_lb) / 2;
if(x[mid] < st) bin_lb = mid;
else bin_rb = mid;
}
lb = bin_lb;
bin_lb = 0, bin_rb = n + 1;
while(bin_rb - bin_lb > 1) {
int mid = (bin_rb + bin_lb) / 2;
if(x[mid] > st) bin_rb = mid;
else bin_lb = mid;
}
ll sum = 0;
rb = bin_rb;
sum += min(st - x[lb], x[rb] - st);
if(st - x[lb] <= x[rb] - st) rb--;
else lb++, turn = 1;
// cout << lb << ' ' << rb << ' ' << sum << ' ' << turn << '\n';
while(lb > 1 || rb < n) {
if(!turn) {
bin_lb = 0, bin_rb = lb;
while(bin_rb - bin_lb > 1) {
int mid = (bin_lb + bin_rb) / 2;
if(st_ld.get(mid, lb - 1) <= x[rb + 1]) bin_rb = mid;
else bin_lb = mid;
}
sum += x[lb] - x[bin_rb];
lb = bin_rb;
if(rb < n) sum += x[++rb] - x[lb];
} else {
bin_lb = rb; bin_rb = n + 1;
while(bin_rb - bin_lb > 1) {
int mid = (bin_rb + bin_lb) / 2;
if(st_rd.get(rb + 1, mid) < -x[lb - 1]) bin_lb = mid;
else bin_rb = mid;
}
sum += x[bin_lb] - x[rb];
rb = bin_lb;
if(lb > 1) sum += x[rb] - x[--lb];
}
// cout << lb << ' ' << rb << ' ' << sum << ' ' << turn << '\n';
turn = !turn;
}
cout << sum << '\n';
}
}
Compilation message
travel.cpp: In instantiation of 'void SparseTable<T>::init(std::vector<_Tp>&, T (*)(T, T)) [with T = long long int]':
travel.cpp:48:59: required from here
travel.cpp:23:66: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
23 | st[k][i] = F(st[k - 1][i], st[k - 1][i + (1 << k - 1)]);
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
596 KB |
Output is correct |
| 3 |
Correct |
1 ms |
596 KB |
Output is correct |
| 4 |
Correct |
1 ms |
596 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
596 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
