#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200001;
const int lg = 19;
int lg2[N], mn[N][lg], mx[N][lg];
int query_min(int l, int r) {
int j = lg2[r - l + 1];
return min(mn[l][j], mn[r - (1 << j) + 1][j]);
}
int query_max(int l, int r) {
int j = lg2[r - l + 1];
return max(mx[l][j], mx[r - (1 << j) + 1][j]);
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int n, q;
cin >> n;
vector<int> x(n), ll(n), rr(n);
for (int i = 0; i < n; i++) {
cin >> x[i];
ll[i] = rr[i] = i;
}
for (int i = 1; i < n; i++) {
int dist = x[i] - x[i - 1];
int l = i, r = n - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (x[mid] - x[i] < dist) l = mid;
else r = mid - 1;
}
if (x[l] - x[i] < dist) rr[i - 1] = l; // if i'm going left to i - 1, rb must > l
}
for (int i = 0; i < n - 1; i++) {
int dist = x[i + 1] - x[i];
int l = 0, r = i;
while (l < r) {
int mid = (l + r) / 2;
if (x[i] - x[mid] <= dist) r = mid;
else l = mid + 1;
}
if (x[i] - x[l] <= dist) ll[i + 1] = l; // if i'm going right to i + 1, lb must < l
}
// for (int i = 0; i < n; i++) cout << ll[i] << ' ' << rr[i] << '\n';
lg2[1] = 0;
for (int i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1;
for (int i = 0; i < n; i++) mx[i][0] = rr[i], mn[i][0] = ll[i];
for (int j = 1; j < lg; j++) {
for (int i = 0; i + (1 << j) - 1 < n; i++) {
mn[i][j] = min(mn[i][j - 1], mn[i + (1 << (j - 1))][j - 1]);
mx[i][j] = max(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
}
}
cin >> q;
while (q--) {
int s, ans = 0;
cin >> s;
int left = 0, lb, rb, cp;
if (s >= x.back()) left = 1, lb = rb = n - 1, ans += s - x.back(), cp = n - 1;
else if (s > x.front()) {
auto it = lower_bound(x.begin(), x.end(), s);
int prv, nxt;
if ((*it) == s) {
prv = *prev(it);
nxt = *next(it);
if (s - prv <= nxt - s) lb = it - x.begin() - 1, rb = lb + 1, ans += s - prv, left = 1, cp = lb;
else lb = it - x.begin(), rb = lb + 1, ans += nxt - s, cp = rb;
} else {
prv = *prev(it);
nxt = *it;
if (s - prv <= nxt - s) lb = rb = it - x.begin() - 1, ans += s - prv, left = 1, cp = lb;
else lb = rb = it - x.begin(), ans += nxt - s, cp = lb;
}
} else lb = rb = 0, ans += x.front() - s, cp = 0;
// cout << "ans:" << lb << ' ' << rb << ' ' << ans << '\n';
for (int ti = 0; ti < (lg << 1); ti++) {
if (lb <= 0 && rb > n) break;
if (left && lb > 0) {
int l = 0, r = lb - 1;
while (l < r) {
int mid = (l + r) / 2;
if (rb >= query_max(mid, lb - 1)) r = mid;
else l = mid + 1;
}
ans += abs(x[cp] - x[l]);
lb = cp = l;
// cout << "ans:" << lb << ' ' << rb << ' ' << ans << '\n';
} else if (!left && rb < n - 1) {
int l = rb + 1, r = n - 1;
while (l < r) {
int mid = (l + r + 1) / 2;
if (lb <= query_min(rb + 1, mid)) l = mid;
else r = mid - 1;
}
ans += abs(x[l] - x[cp]);
rb = cp = l;
// cout << "ans:" << lb << ' ' << rb << ' ' << ans << '\n';
}
left ^= 1;
}
// cout << "final ans:" << lb << ' ' << rb << ' ' << ans << '\n';
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4560 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4568 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4560 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4568 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 2 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 3 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 4 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 5 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 6 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 7 |
Incorrect |
235 ms |
69924 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 2 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 3 |
Correct |
2 ms |
6748 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 5 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6744 KB |
Output is correct |
| 7 |
Correct |
1 ms |
6748 KB |
Output is correct |
| 8 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 9 |
Correct |
1 ms |
4444 KB |
Output is correct |
| 10 |
Correct |
1 ms |
4560 KB |
Output is correct |
| 11 |
Correct |
1 ms |
4568 KB |
Output is correct |
| 12 |
Correct |
1 ms |
4440 KB |
Output is correct |
| 13 |
Incorrect |
1 ms |
4444 KB |
Output isn't correct |
| 14 |
Halted |
0 ms |
0 KB |
- |
