#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 2e5 + 2;
const ll linf = 1e18;
int l[N][18], r[N][18], logs[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 1; i < n; i++) l[i][0] = 2 * a[i] - a[i - 1];
for (int j = 1; j < 18; j++) {
for (int i = 1; i < n - (1 << j) + 1; i++) {
l[i][j] = max(l[i][j - 1], l[i + (1 << (j - 1))][j - 1]);
}
}
for (int i = 0; i < n - 1; i++) r[i][0] = 2 * a[i] - a[i + 1];
for (int j = 1; j < 18; j++) {
for (int i = 0; i < n - (1 << j); i++) {
r[i][j] = min(r[i][j - 1], r[i + (1 << (j - 1))][j - 1]);
}
}
int zz = 0;
for (int i = 1; i <= n; i++) {
if ((1 << (zz + 1)) == i) zz += 1;
logs[i] = zz;
}
auto GetLeft = [&] (int p, int q) {
if (p >= q) return 0;
int o = logs[q - p + 1];
return max(l[p][o], l[q - (1 << o) + 1][o]);
};
auto GetRight = [&] (int p, int q) {
if (p >= q) return 0;
int o = logs[q - p + 1];
return min(r[p][o], r[q - (1 << o) + 1][o]);
};
int q; cin >> q;
while (q--) {
int s; cin >> s;
if (s >= a[n - 1]) {
cout << s - a[0] << en;
continue;
}
if (s <= a[0]) {
cout << a[n - 1] - s << en;
continue;
}
int up = (int)(upper_bound(a.begin(), a.end(), s) - a.begin());
int lo = up - 1;
if (a[lo] == s) lo -= 1;
int uu = 0;
ll ans = s;
if (s - a[lo] > a[up] - s) {
uu = 1;
ans = -s;
}
while (1) {
if (uu == 0) {
if (GetLeft(1, lo) <= a[up] || lo <= 0) {
ans += a[n - 1] - 2 * a[0];
cout << ans << en;
break;
}
int lef = 1, rig = lo, gde = -1;
while (lef <= rig) {
int mid = lef + rig >> 1;
if (GetLeft(mid, lo) > a[up]) {
lef = mid + 1;
gde = mid;
}
else rig = mid - 1;
}
assert(gde < lo && gde != -1);
ans -= 2 * a[gde];
uu ^= 1;
lo = gde - 1;
up += 1;
continue;
}
if (GetRight(up, n - 2) > a[lo] || up >= n - 1) {
ans += 2 * a[n - 1] - a[0];
cout << ans << en;
break;
}
int lef = up, rig = n - 2, gde = -1;
while (lef <= rig) {
int mid = lef + rig >> 1;
if (GetRight(up, mid) <= a[lo]) {
rig = mid - 1;
gde = mid;
}
else lef = mid + 1;
}
assert(gde > up);
ans += 2 * a[gde];
uu ^= 1;
up = gde + 1;
lo -= 1;
}
}
return 0;
}
Compilation message
travel.cpp: In function 'int main()':
travel.cpp:75:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int mid = lef + rig >> 1;
| ~~~~^~~~~
travel.cpp:96:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
96 | int mid = lef + rig >> 1;
| ~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 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 |
Correct |
1 ms |
592 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
324 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 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 |
Correct |
1 ms |
592 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
324 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 14 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
324 KB |
Output is correct |
| 4 |
Correct |
0 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
328 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Incorrect |
136 ms |
32688 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 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 |
Correct |
1 ms |
592 KB |
Output is correct |
| 6 |
Correct |
1 ms |
596 KB |
Output is correct |
| 7 |
Correct |
1 ms |
596 KB |
Output is correct |
| 8 |
Correct |
1 ms |
212 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
324 KB |
Output is correct |
| 11 |
Correct |
1 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
340 KB |
Output is correct |
| 13 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 14 |
Halted |
0 ms |
0 KB |
- |
