#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
const int nax = 200005;
int N, Q;
i64 X[nax];
void solve(int p) {
int l = 0, r = N + 1, res = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (X[mid] <= p) res = mid, l = mid + 1;
else r = mid - 1;
}
int L = res;
l = 0, r = N + 1, res = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (X[mid] > p) res = mid, r = mid - 1;
else l = mid + 1;
}
int R = res;
i64 ans = 0, cur = p;
// cout << "first : " << L << ' ' << R << ' ' << ans << '\n';
if (abs(cur - X[L]) <= abs(X[R] - cur)) {
ans += abs(cur - X[L]);
cur = X[L];
L -= 1;
}
else {
ans += abs(cur - X[R]);
cur = X[R];
R += 1;
}
// cout << "second : " << L << ' ' << R << ' ' << ans << '\n';
while (L >= 1 || R <= N) {
// cout << L << ' ' << R << ' ' << ans << ' ' << cur << '\n';
// cout << abs(cur - X[L]) << ' ' << abs(X[R] - cur) << '\n';
if (abs(cur - X[L]) <= abs(X[R] - cur)) {
i64 dis = abs(X[R] - cur);
l = 0, r = N + 1, res = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (X[mid] >= cur - dis) {
res = mid;
r = mid - 1;
}
else l = mid + 1;
}
if (res == 0) res = 1;
ans += abs(cur - X[res]);
cur = X[res];
L = res - 1;
}
else {
i64 dis = abs(X[L] - cur);
l = 0, r = N + 1, res = -1;
while (l <= r) {
int mid = (l + r) >> 1;
if (X[mid] <= cur + dis) {
res = mid;
l = mid + 1;
}
else r = mid - 1;
}
if (res == N + 1) res = N;
ans += abs(cur - X[res]);
cur = X[res];
R = res + 1;
}
if (L == 0 || R == N + 1) break;
}
ans += abs(cur - X[1]);
ans += abs(cur - X[N]);
cout << ans << '\n';
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> N;
for (int i = 1; i <= N; i++) cin >> X[i];
X[0] = -1E14; X[N + 1] = 1E14;
cin >> Q;
while (Q--) {
int o; cin >> o;
solve(o);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
344 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
13 |
Halted |
0 ms |
0 KB |
- |