Submission #1185737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185737		avighna	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	3082 ms	385036 KiB

timeleap

#include <bits/stdc++.h>

typedef long long ll;

const ll inf = 1e15;

struct Query {
  ll a, b, c, d;
  int i;
};

template <typename T> class SparseTable {
public:
  int max_p;
  std::vector<T> orig;
  std::vector<std::vector<T>> min, max;

  SparseTable(const std::vector<T> &x) : orig(x) {
    const int n = x.size();
    max_p = std::floor(std::log2(n));
    min = std::vector(max_p + 1, std::vector<T>(n));
    max = std::vector(max_p + 1, std::vector<T>(n));
    for (int i = 0; i < n; ++i) {
      min[0][i] = max[0][i] = x[i];
    }
    for (int p = 1; p <= max_p; ++p) {
      for (int i = 0; i < n - (1 << (p - 1)); ++i) {
        min[p][i] = std::min(min[p - 1][i], min[p - 1][i + (1 << (p - 1))]);
        max[p][i] = std::max(max[p - 1][i], max[p - 1][i + (1 << (p - 1))]);
      }
    }
  }

  T query_min(int a, int b) {
    if (a == b) {
      return orig[a];
    }
    int p = std::ceil(std::log2(b - a + 1)) - 1;
    return std::min(min[p][a], min[p][b - (1 << p) + 1]);
  }
  T query_max(int a, int b) {
    if (a == b) {
      return orig[a];
    }
    int p = std::ceil(std::log2(b - a + 1)) - 1;
    return std::max(max[p][a], max[p][b - (1 << p) + 1]);
  }
};

std::vector<ll> solve(int n, int q, std::vector<ll> l, std::vector<ll> r,
                      std::vector<Query> queries) {
  l.push_back(inf);
  r.push_back(inf + 1);
  auto corr = [&](ll a, ll b, ll c, ll d) -> std::pair<ll, ll> {
    ll ans = 0;
    for (int i = a < c ? a : a - 1; (a < c and i < c) or (a > c and i >= c);) {
      if (b < l[i]) {
        b = l[i];
      } else if (b > r[i] - 1) {
        ans += b - (r[i] - 1);
        b = r[i] - 1;
      }
      b++;
      i += a < c ? 1 : -1;
    }
    if (b > d) {
      ans += b - d;
      b = d;
    }
    return {ans, b};
  };

  // your code here
  int lim = std::log2(n) + 1;
  std::vector ansl(n, std::vector<std::pair<ll, ll>>(lim)),
      ansr(n, std::vector<std::pair<ll, ll>>(lim));
  for (int i = 0; i < n; ++i) {
    ansl[i][0] = {0, l[i] + 1};
    ansr[i][0] = {0, r[i]}; // 0 jumps means we don't need anything
    if (i != n - 1) {
      ll v1 = std::max(0LL, ansl[i][0].second - (r[i + 1] - 1));
      ll v2 = std::max(0LL, ansr[i][0].second - (r[i + 1] - 1));
      ansl[i][0].first += v1;
      ansr[i][0].first += v2;
      ansl[i][0].second -= v1;
      ansr[i][0].second -= v2;
    }
  }
  auto _ansl = [&](int i, int x) -> std::pair<ll, ll> {
    ll cost = 0, time = l[i];
    for (int bt = 0; bt < lim; ++bt) {
      if (x & (1 << bt)) {
        cost += ansl[i][bt].first;
        time = ansl[i][bt].second;
        i += (1 << bt);
      }
    }
    return {cost, time};
  };
  auto _ansr = [&](int i, int x) -> std::pair<ll, ll> {
    ll cost = 0, time = r[i] - 1;
    for (int bt = 0; bt < lim; ++bt) {
      if (x & (1 << bt)) {
        cost += ansr[i][bt].first;
        time = ansr[i][bt].second;
        i += (1 << bt);
      }
    }
    return {cost, time};
  };
  std::vector<ll> orig_max(n), orig_min(n);
  for (int i = 0; i < n; ++i) {
    orig_max[i] = l[i] - i;
    orig_min[i] = r[i] - i - 1;
  }
  SparseTable<ll> table_max(orig_max), table_min(orig_min);
  auto _ans = [&](int i, int x, ll t) -> std::pair<ll, ll> {
    int idx1 =
        *std::ranges::partition_point(std::views::iota(i, n), [&](int j) {
          return table_max.query_max(i, j) <= t - i;
        }); // first index such that l <= t_then is not true
    int idx2 =
        *std::ranges::partition_point(std::views::iota(i, n), [&](int j) {
          return t - i <= table_min.query_min(i, j);
        }); // first index such that t_then <= r-1 is not true

    ll free_jumps = std::max(0, std::min(idx1, idx2) - i);
    if (x <= free_jumps) {
      int r_idx = i + x;
      std::pair<ll, ll> p = {0, t + x};
      if (t + x > r[r_idx] - 1) {
        int del = t + x - (r[r_idx] - 1);
        p.first += del;
        p.second -= del;
      }
      return p;
    }

    // jump ahead how much ever we can
    if (idx1 < idx2) {
      auto p = _ansl(idx1, x - free_jumps);
      return {p.first, p.second};
    } else {
      // we're to the right (>=) of r[idx2], we need to get to r[idx2]-1
      ll t_cur = t + free_jumps;
      ll cost = t_cur - (r[idx2] - 1); // this does that
      t_cur = r[idx2] - 1;             // this does that
      auto p = _ansr(idx2, x - free_jumps);
      return {cost + p.first, p.second};
    }
  };
  for (int bt = 1; bt < lim; ++bt) {
    for (int i = 0; i + (1 << bt) < n; ++i) {
      {
        auto [ans1, t1] = ansl[i][bt - 1];
        auto [ans2, t2] = _ans(i + (1 << (bt - 1)), 1 << (bt - 1), t1);
        ansl[i][bt] = {ans1 + ans2, t2};
      }
      {
        auto [ans1, t1] = ansr[i][bt - 1];
        auto [ans2, t2] = _ans(i + (1 << (bt - 1)), 1 << (bt - 1), t1);
        ansr[i][bt] = {ans1 + ans2, t2};
      }
    }
  }

  // check values
  for (int bt = 0; bt < lim; ++bt) {
    for (int i = 0; i + (1 << bt) < n; ++i) {
      {
        auto exp = corr(i, l[i], i + (1 << bt), r[i + (1 << bt)] - 1);
        if (exp != ansl[i][bt]) {
          std::cout << "error: ansl index: " << i << ", bt: " << bt
                    << " = {cost: " << ansl[i][bt].first
                    << ", time: " << ansl[i][bt].second << "}\n";
          std::cout << "expected: {cost: " << exp.first
                    << ", time: " << exp.second << "}\n";
          corr(i, l[i], i + (1 << bt), r[i + (1 << bt)] - 1);
          exit(0);
        }
      }
      {
        auto exp = corr(i, r[i] - 1, i + (1 << bt), r[i + (1 << bt)] - 1);
        if (exp != ansr[i][bt]) {
          std::cout << "error: ansr index: " << i << ", bt: " << bt
                    << " = {cost: " << ansr[i][bt].first
                    << ", time: " << ansr[i][bt].second << "}\n";
          std::cout << "expected: {cost: " << exp.first
                    << ", time: " << exp.second << "}\n";
          corr(i, r[i] - 1, i + (1 << bt), r[i + (1 << bt)] - 1);
          exit(0);
        }
      }
    }
  }

  std::vector<ll> ans(q);
  for (auto &[a, b, c, d, i] : queries) {
    if (a == c) {
      continue;
    }
    auto [cost, time] = _ans(a, c - a - 1, b);
    if (time < l[c - 1]) {
      time = l[c - 1];
    } else if (time > r[c - 1] - 1) {
      cost += time - (r[c - 1] - 1);
      time = r[c - 1] - 1;
    }
    time++;
    if (time > d) {
      cost += time - d;
    }
    ans[i] = cost;
  }
  return ans;
}

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

  int n, q;
  std::cin >> n >> q;
  std::vector<ll> l(n - 1), r(n - 1);
  for (int i = 0; i < n - 1; ++i) {
    std::cin >> l[i] >> r[i];
  }
  std::vector<Query> q1, q2;
  for (int i = 0, a, b, c, d, t; i < q; ++i) {
    std::cin >> t >> a >> b >> c >> d;
    --a, --c;
    if (a <= c) {
      q1.push_back({a, b, c, d, i});
    } else {
      q2.push_back({a, b, c, d, i});
    }
  }
  auto ans1 = solve(n, q, l, r, q1);
  std::reverse(l.begin(), l.end());
  std::reverse(r.begin(), r.end());
  for (auto &[a, b, c, d, i] : q2) {
    a = n - a - 1, c = n - c - 1;
  }
  auto ans2 = solve(n, q, l, r, q2);
  for (int i = 0; i < q; ++i) {
    std::cout << std::max(ans1[i], ans2[i]) << '\n';
  }
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 30
• Subtask 3: 0 / 66