#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
const int L = 20;
#define int ll
int n, q;
int a[N], x[N], y[N];
struct SparseTable {
vector<int> lg;
vector<int> mn[L];
vector<int> mx[L];
SparseTable(int n, int a[]) {
lg.resize(n + 1);
for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
for (int i = 0; i < L; ++i) mn[i].resize(n + 1);
for (int i = 0; i < L; ++i) mx[i].resize(n + 1);
for (int i = 1; i <= n; ++i) mn[0][i] = a[i];
for (int i = 1; i <= n; ++i) mx[0][i] = a[i];
for (int h = 1; h < L; ++h) {
for (int i = 1; i + (1 << h) - 1 <= n; ++i) {
mx[h][i] = max(mx[h - 1][i], mx[h - 1][i + (1 << (h - 1))]);
mn[h][i] = min(mn[h - 1][i], mn[h - 1][i + (1 << (h - 1))]);
}
}
}
int get_max(int l, int r) {
int p = lg[r - l + 1];
return max(mx[p][l], mx[p][r - (1 << p) + 1]);
}
int get_min(int l, int r) {
int p = lg[r - l + 1];
return min(mn[p][l], mn[p][r - (1 << p) + 1]);
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i < n; ++i) x[i] = 2 * a[i] - a[i + 1];
for (int i = 1; i <= n; ++i) y[i] = 2 * a[i] - a[i - 1];
SparseTable t1(n - 1, x), t2(n, y);
cin >> q;
while (q--) {
int x;
cin >> x;
int low = 1, high = n, pos = 0;
while (low <= high) {
int mid = (low + high) / 2;
if (a[mid] <= x) {
low = mid + 1;
pos = mid;
} else {
high = mid - 1;
}
}
int l = pos, r = pos + 1;
int cord = x;
ll ans = 0;
while (l != 0 || r != n + 1) {
cout << l << " " << r << "\n";
if (l == 0) {
ans += a[n] - cord;
r = n + 1;
break;
}
if (r == n + 1) {
ans += cord - a[1];
l = 0;
break;
}
if (abs(cord - a[l]) <= abs(cord - a[r])) { // merge in stanga
if (l == 1) {
ans += abs(cord - a[1]);
cord = a[1];
l = 0;
continue;
}
int low = 2, high = l, sol = l + 1;
while (low <= high) {
int mid = (low + high) / 2;
// 2 * a[mid] - a[mid - 1]
if (t2.get_max(mid, l) <= a[r]) {
high = mid - 1;
sol = mid;
} else {
low = mid + 1;
}
}
ans += abs(cord - a[sol - 1]);
cord = a[sol - 1];
l = sol - 2;
} else { // merge in dreapta
if (r == n) {
ans += abs(cord - a[n]);
cord = a[n];
r = n + 1;
continue;
}
int low = r, high = n - 1, sol = r - 1;
while (low <= high) {
int mid = (low + high) / 2;
// 2 * a[mid] - a[mid + 1]
if (t1.get_min(r, mid) > a[l]) {
low = mid + 1;
sol = mid;
} else {
high = mid - 1;
}
}
ans += abs(cord - a[sol + 1]);
cord = a[sol + 1];
r = sol + 2;
}
}
cout << ans << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
