#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e5+2, LOG = 20;
int mx[LOG][mxN], mn[LOG][mxN], lg[mxN];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
lg[1] = 0;
for (int i = 2; i < mxN; ++i) {
lg[i] = lg[i/2]+1;
}
int n;
cin >> n;
int a[n+2]; set<pair<int, int>> s;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
s.insert({a[i], i});
}
for (int i = 1; i <= n; ++i) {
if (i != 1) mx[0][i] = 2*a[i] - a[i-1];
if (i != n) mn[0][i] = 2*a[i] - a[i+1];
}
for (int i = 1; i < LOG; ++i) {
for (int j = 1; j <= n; ++j) {
mx[i][j] = max(mx[i-1][j], mx[i-1][j + (1 << (i - 1))]);
mn[i][j] = min(mn[i-1][j], mn[i-1][j + (1 << (i - 1))]);
}
}
auto mnq = [&](int l, int r) {
return min(mn[lg[r-l+1]][l], mn[lg[r-l+1]][r-(1 << (r-l+1))]);
};
auto mxq = [&](int l, int r) {
return max(mx[lg[r-l+1]][l], mx[lg[r-l+1]][r-(1 << (r-l+1))]);
};
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
auto it = s.lower_bound({x, 0});
int b = 0;
if (it != s.end()) {
b = (*it).second;
if (abs(x-a[b]) > abs(x-a[b-1])) b--;
}
if (it == s.end() || (*it).first != 1) {
b = n;
}
long long ans = abs(x-a[b]) + a[n] - a[1]; // verovatno staje u int
int l = b, r = b; // dir = 1 => idi desno, dir = 0 => idi levo.
bool dir = (b == 1 ? 1 : (b == n ? 0 : (a[b] - a[b-1] <= a[b+1] - a[b] ? 0 : 1)));
while (l != 1 && r != n) {
if (dir) {
if (r == n-1 || mnq(r+1, n-1) > a[l-1]) {
ans += a[n] - a[l];
break;
}
int le = r+1, ri = n-1, t = 0;
while (le <= ri) {
int mid = (le + ri)/2;
if (mnq(r+1, mid) <= a[l-1]) {
t = mid;
ri = mid-1;
}
else {
le = mid+1;
}
}
ans += a[t] - a[l];
r = t;
}
else {
if (l == 2 || mxq(2, l-1) <= a[r+1]) {
ans += a[r] - a[1];
break;
}
int le = 2, ri = n-1, t = 0;
while (le <= ri) {
int mid = (le + ri)/2;
if (mxq(mid, l-1) > a[r+1]) {
t = mid;
le = mid+1;
}
else {
ri = mid-1;
}
}
ans += a[r] - a[t];
l = t;
}
dir ^= 1;
}
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
31320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
31324 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
