#include <bits/stdc++.h>
#define int long long
int give_sum(int l, int r, std::vector<int> &pref)
{
if (l > r)
{
return 0;
}
if (l == 0)
{
return pref[r];
}
return pref[r] - pref[l - 1];
}
signed main()
{
int n;
std::cin >> n;
std::vector<int> x(n);
std::vector<int> pref(n);
for (int i = 0; i < n; i++)
{
std::cin >> x[i];
}
std::vector<int> prev(n);
for (int i = 0; i < n; i++)
{
if (i == n - 1)
{
prev[i] = 0;
continue;
}
int last = 0;
for (int j = i; j >= 1; j--)
{
if (x[i + 1] - x[j] < x[j] - x[j - 1])
{
last = j;
break;
}
}
// std::cout << i << ' ' << last << std::endl;
prev[i] = last;
}
std::vector<int> next(n);
for (int i = 0; i < n; i++)
{
if (i == 0)
{
next[i] = n - 1;
continue;
}
int last = n - 1;
for (int j = i; j < n - 1; j++)
{
if (x[j] - x[i - 1] <= x[j + 1] - x[j])
{
last = j;
break;
}
}
// std::cout << i << ' ' << next[i] << ' ' << last << std::endl;
next[i] = last;
}
// exit(0);
std::vector<int> ans(n);
for (int i = 0; i < n; i++)
{
int l = i, r = i;
int j = i;
while ((r - l + 1) != n)
{
//'std::cout << l << ' ' << r << ' ' << j << ' ' << next[j] << ' ' << prev[j] << std::endl;
if (next[j] != j)
{
r = next[j];
ans[i] += x[r] - x[j];
j = r;
}
else
{
l = prev[j];
ans[i] += x[j] - x[l];
j = l;
}
}
}
int q;
std::cin >> q;
for (int i = 0; i < q; i++)
{
int now;
std::cin >> now;
int l = 0, r = x.size();
while (l + 1 < r)
{
int mid = (l + r) / 2;
if (x[mid] <= now)
{
l = mid;
}
else
{
r = mid;
}
}
int cur = 0;
int now_ind = -1;
if (r == x.size())
{
cur += now - x.back();
now_ind = l;
}
else
{
if (std::abs(x[l] - now) <= std::abs(x[r] - now))
{
now_ind = l;
cur += std::abs(x[l] - now);
}
else
{
now_ind = r;
cur += std::abs(x[r] - now);
}
}
std::cout << ans[now_ind] + cur << std::endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |