Submission #1136110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136110		fzyzzz_z	Bitaro's travel (JOI23_travel)	C++20	100 / 100	135 ms	34368 KiB

travel

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

template <typename T, typename F>
class SparseTable {
public:
  int n;
  vector<vector<T>> mat;
  F func;

  vector<int> pre;

  SparseTable(const vector<T>& a, const F& f) : func(f) {
    n = static_cast<int>(a.size());
    for (int i = 0; i <= n; ++i) {
      pre.push_back(32 - __builtin_clz(i) - 1);
    }
    int max_log = 32 - __builtin_clz(n);
    mat.resize(max_log);
    mat[0] = a;
    for (int j = 1; j < max_log; j++) {
      mat[j].resize(n - (1 << j) + 1);
      for (int i = 0; i <= n - (1 << j); i++) {
        mat[j][i] = func(mat[j - 1][i], mat[j - 1][i + (1 << (j - 1))]);
      }
    }
  }

  T get(int from, int to) const {
    assert(0 <= from && from <= to && to <= n - 1);
    // int lg = 32 - __builtin_clz(to - from + 1) - 1;
    int lg = pre[to - from + 1];
    return func(mat[lg][from], mat[lg][to - (1 << lg) + 1]);
  }
};

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

  int n;
  cin >> n;
  vector<int> a(n);
  for (auto& x : a) cin >> x;

  vector<int> switch_left(n), switch_right(n);
  for (int i = 0; i < n; ++i) {
    if (i + 1 < n) { // if x at a[i], and L >= this val, you switch
      switch_left[i] = a[i] - (a[i + 1] - a[i]);
    } else {
      switch_left[i] = -1;
    }

    if (i) { // if x at a[i], and R <= this val, you switch
      switch_right[i] = a[i] + (a[i] - a[i - 1] - 1);
    } else {
      switch_right[i] = 1e9 + 1;
    }
  }

  // switch_left only care about min
  SparseTable sl(switch_left, [&](int x, int y) { return min(x, y); });
  SparseTable sr(switch_right, [&](int x, int y) { return max(x, y); });

  vector<ll> ans(n, 0);
  for (int start = 0; start < n; ++start) {
    int d0 = (start == 0 ? 1e9 + 10 : a[start] - a[start - 1]);
    int d1 = (start == n - 1 ? 1e9 + 10 : a[start + 1] - a[start]);

    int l = start, r = start;
    int dir = (d0 <= d1 ? 0 : 1);

    while (0 < l && r < n - 1) {
      if (dir) { // going right, at a[l] right now
        int lo = r, hi = n - 1;
        while (lo < hi) {
          int md = (lo + hi + 1) / 2;
          if (sl.get(r, md) > a[l - 1]) {
            lo = md;
          } else {
            hi = md - 1;
          }
        }
        if (lo != n - 1) lo++;

        ans[start] += a[lo] - a[l];
        dir ^= 1;
        r = lo;
      } else { // going left, at a[r] right now
        int lo = 0, hi = l;
        while (lo < hi) {
          int md = (lo + hi) / 2;
          if (sr.get(md, l) < a[r + 1]) {
            hi = md;
          } else {
            lo = md + 1;
          }
        }
        if (lo != 0) lo--;

        ans[start] += a[r] - a[lo];
        dir ^= 1;
        l = lo;
      }
    }
    if (0 < l) {
      ans[start] += a[r] - a[0];
    }
    if (r < n - 1) {
      ans[start] += a[n - 1] - a[l];
    }
  }

  int q;
  cin >> q;
  while (q--) {
    int x;
    cin >> x;
    int lo = 0, hi = n - 1;
    while (lo < hi) {
      int md = (lo + hi) / 2;
      if (a[md] >= x) {
        hi = md;
      } else {
        lo = md + 1;
      }
    }
    int best = -1, d = 1e9 + 10;
    for (int i = max(0, lo - 3); i <= min(n - 1, lo + 3); ++i) {
      if (abs(a[i] - x) < d) {
        d = abs(a[i] - x);
        best = i;
      }
    }
    assert(best != -1);

    cout << (ans[best] + abs(a[best] - x)) << "\n";
  }

  return 0;
}

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