Submission #1171921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171921		fryingduc	Bitaro's travel (JOI23_travel)	C++20	100 / 100	256 ms	70084 KiB

travel

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
const int LG = 18;
int n;
long long a[maxn];
long long res[maxn];
long long df[maxn];
long long sl[maxn][LG + 1], sr[maxn][LG + 1];

long long getl(int l, int r) {
  int p = 31 - __builtin_clz(r - l + 1);
  return max(sl[l][p], sl[r - (1 << p) + 1][p]);
}

long long getr(int l, int r) {
  int p = 31 - __builtin_clz(r - l + 1);
  return min(sr[l][p], sr[r - (1 << p) + 1][p]);
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  a[n + 1] = 2e12;
  a[0] = -1e12;
  for (int i = 1; i <= n + 1; ++i) {
    df[i] = a[i] - a[i - 1];
    sl[i][0] = 2ll * a[i] - a[i - 1];
    sr[i][0] = 2ll * a[i] - a[i + 1];
  }
  for (int j = 1; j <= LG; ++j) {
    for (int i = 1; i + (1 << j) <= n + 1; ++i) {
      sl[i][j] = max(sl[i][j - 1], sl[i + (1 << (j - 1))][j - 1]);
      sr[i][j] = min(sr[i][j - 1], sr[i + (1 << (j - 1))][j - 1]);
    }
  }
  queue<array<int, 4>> q;
  for (int i = 1; i <= n; ++i) {
    q.push({i, i, i, (a[i + 1] - a[i] < a[i] - a[i - 1])});
  }
  while (!q.empty()) {
    auto [l, r, id, turn] = q.front();
    q.pop();
    if (l == 1 and r == n) continue;
    if (!turn) {
      int le = 2, ri = l, pos = l;
      while (le <= ri) {
        int mid = (le + ri) >> 1;
        if (getl(mid, l) <= a[r + 1]) {
          pos = mid - 1;
          ri = mid - 1;
        } else {
          le = mid + 1;
        }
      }
      res[id] += a[l] - a[pos];
      if (pos == 1) {
        if (r < n) {
          res[id] += a[n] - a[1];
        }
      } else {
        res[id] += a[r + 1] - a[pos];      
//        debug("turn 0", pos, r + 1, id, res[id]);
        q.push({pos, r + 1, id, turn ^ 1});
      }
    } else {
      int le = r, ri = n - 1, pos = r;
      while (le <= ri) {
        int mid = (le + ri) >> 1;
        if (getr(r, mid) > a[l - 1]) {
          pos = mid + 1;
          le = mid + 1;
        } else {
          ri = mid - 1;
        }
      }
      res[id] += a[pos] - a[r];
      if (pos == n) {
        if (l > 1) {
          res[id] += a[n] - a[1];
        }
      } else {
        res[id] += a[pos] - a[l - 1];
//        debug("turn 1", l - 1, pos, id, res[id]);
        q.push({l - 1, pos, id, turn ^ 1});
      }
    }
  }
//  for (int i = 1; i <= n; ++i) {
//    debug(i, res[i]);
//  }
  int qx; cin >> qx;
  while (qx--) {
    int x; cin >> x;
    int p = upper_bound(a + 1, a + n + 1, x) - a - 1;
    if (x - a[p] > a[p + 1] - x) {
      ++p;
    }
    cout << res[p] + abs(x - a[p]) << '\n';
  }
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 55 / 55