fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. static const ll INF = (1LL << 62);
  7.  
  8. int main() {
  9.     ios::sync_with_stdio(false);
  10.     cin.tie(nullptr);
  11.  
  12.     int N;
  13.     cin >> N;
  14.  
  15.     vector<ll> X(N + 2);
  16.     for (int i = 1; i <= N; ++i) cin >> X[i];
  17.  
  18.     int Q;
  19.     cin >> Q;
  20.  
  21.     if (N == 1) {
  22.         while (Q--) {
  23.             ll S;
  24.             cin >> S;
  25.             cout << llabs(S - X[1]) << '\n';
  26.         }
  27.         return 0;
  28.     }
  29.  
  30.     // A[i] = 2*X[i] - X[i-1]   (i = 2..N)
  31.     // B[i] = 2*X[i] - X[i+1]   (i = 1..N-1)
  32.     vector<ll> A(N + 2, -INF), B(N + 2, INF);
  33.     for (int i = 2; i <= N; ++i) A[i] = 2 * X[i] - X[i - 1];
  34.     for (int i = 1; i <= N - 1; ++i) B[i] = 2 * X[i] - X[i + 1];
  35.  
  36.     int LG = 1;
  37.     while ((1 << LG) <= N + 1) ++LG;
  38.  
  39.     vector<int> lg(N + 2, 0);
  40.     for (int i = 2; i <= N + 1; ++i) lg[i] = lg[i / 2] + 1;
  41.  
  42.     // Sparse table max for A
  43.     vector<vector<ll>> stMax(LG, vector<ll>(N + 2, -INF));
  44.     // Sparse table min for B
  45.     vector<vector<ll>> stMin(LG, vector<ll>(N + 2, INF));
  46.  
  47.     for (int i = 2; i <= N; ++i) stMax[0][i] = A[i];
  48.     for (int i = 1; i <= N - 1; ++i) stMin[0][i] = B[i];
  49.  
  50.     for (int k = 1; k < LG; ++k) {
  51.         int len = 1 << k;
  52.         int half = len >> 1;
  53.  
  54.         for (int i = 2; i + len - 1 <= N; ++i) {
  55.             stMax[k][i] = max(stMax[k - 1][i], stMax[k - 1][i + half]);
  56.         }
  57.         for (int i = 1; i + len - 1 <= N - 1; ++i) {
  58.             stMin[k][i] = min(stMin[k - 1][i], stMin[k - 1][i + half]);
  59.         }
  60.     }
  61.  
  62.     auto getMaxA = [&](int l, int r) -> ll {
  63.         int k = lg[r - l + 1];
  64.         return max(stMax[k][l], stMax[k][r - (1 << k) + 1]);
  65.     };
  66.  
  67.     auto getMinB = [&](int l, int r) -> ll {
  68.         int k = lg[r - l + 1];
  69.         return min(stMin[k][l], stMin[k][r - (1 << k) + 1]);
  70.     };
  71.  
  72.     while (Q--) {
  73.         ll S;
  74.         cin >> S;
  75.  
  76.         // Find nearest point to S, tie -> smaller coordinate
  77.         int pos = lower_bound(X.begin() + 1, X.begin() + N + 1, S) - X.begin();
  78.         int k;
  79.  
  80.         if (pos == 1) k = 1;
  81.         else if (pos == N + 1) k = N;
  82.         else {
  83.             ll leftDist = S - X[pos - 1];
  84.             ll rightDist = X[pos] - S;
  85.             if (leftDist <= rightDist) k = pos - 1;
  86.             else k = pos;
  87.         }
  88.  
  89.         ll ans = llabs(S - X[k]);
  90.         int l = k, r = k;
  91.  
  92.         // side = 0: currently at left endpoint
  93.         // side = 1: currently at right endpoint
  94.         int side = 0;
  95.  
  96.         while (l > 1 || r < N) {
  97.             bool goLeft;
  98.  
  99.             if (l == 1) {
  100.                 goLeft = false;
  101.             } else if (r == N) {
  102.                 goLeft = true;
  103.             } else {
  104.                 ll dL, dR;
  105.                 if (side == 0) {
  106.                     // currently at X[l]
  107.                     dL = X[l] - X[l - 1];
  108.                     dR = X[r + 1] - X[l];
  109.                 } else {
  110.                     // currently at X[r]
  111.                     dL = X[r] - X[l - 1];
  112.                     dR = X[r + 1] - X[r];
  113.                 }
  114.                 goLeft = (dL <= dR);
  115.             }
  116.  
  117.             if (goLeft) {
  118.                 ll T = X[r + 1];
  119.  
  120.                 int lo = 0, hi = l - 1, best = 0;
  121.                 while (lo <= hi) {
  122.                     int mid = (lo + hi) >> 1;
  123.                     bool ok = true;
  124.                     if (mid > 0) {
  125.                         int L = l - mid + 1;
  126.                         int R = l;
  127.                         ok = (getMaxA(L, R) <= T);
  128.                     }
  129.                     if (ok) {
  130.                         best = mid;
  131.                         lo = mid + 1;
  132.                     } else {
  133.                         hi = mid - 1;
  134.                     }
  135.                 }
  136.  
  137.                 l -= best;
  138.                 ans += X[l + best] - X[l];
  139.                 side = 0;
  140.             } else {
  141.                 ll T = X[l - 1];
  142.  
  143.                 int lo = 0, hi = N - r, best = 0;
  144.                 while (lo <= hi) {
  145.                     int mid = (lo + hi) >> 1;
  146.                     bool ok = true;
  147.                     if (mid > 0) {
  148.                         int L = r;
  149.                         int R = r + mid - 1;
  150.                         ok = (getMinB(L, R) >= T);
  151.                     }
  152.                     if (ok) {
  153.                         best = mid;
  154.                         lo = mid + 1;
  155.                     } else {
  156.                         hi = mid - 1;
  157.                     }
  158.                 }
  159.  
  160.                 r += best;
  161.                 ans += X[r] - X[r - best];
  162.                 side = 1;
  163.             }
  164.         }
  165.  
  166.         cout << ans << '\n';
  167.     }
  168.  
  169.     return 0;
  170. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/XT3pK1
language:
C++14 (clang 8.0)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!