Submission #1187515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187515		avighna	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	30 / 100	2239 ms	385656 KiB

timeleap

#include <bits/stdc++.h>

typedef long long ll;

const ll inf = 1e15;

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

void solve(int n, int q, std::vector<ll> l, std::vector<ll> r,
           std::vector<Query> queries, std::vector<ll> &ans) {
  l.push_back(inf);
  r.push_back(inf + 1);
  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;
  }
  int lim = std::log2(n) + 1;
  std::vector jump_max(n, std::vector<ll>(lim)),
      jump_min(n, std::vector<ll>(lim));
  for (int i = 0; i < n; ++i) {
    jump_max[i][0] = l[i] - i;
    jump_min[i][0] = r[i] - i - 1;
  }
  for (int bt = 1; bt < lim; ++bt) {
    for (int i = 0; i < n; ++i) {
      jump_min[i][bt] = jump_min[i][bt - 1];
      jump_max[i][bt] = jump_max[i][bt - 1];
      if (i + (1 << (bt - 1)) < n) {
        if (jump_min[i + (1 << (bt - 1))][bt - 1] < jump_min[i][bt]) {
          jump_min[i][bt] = jump_min[i + (1 << (bt - 1))][bt - 1];
        }
        if (jump_max[i + (1 << (bt - 1))][bt - 1] > jump_max[i][bt]) {
          jump_max[i][bt] = jump_max[i + (1 << (bt - 1))][bt - 1];
        }
      }
    }
  }
  auto binary_search = [&](int i, ll t) -> std::pair<ll, ll> {
    int idx1 = i, idx2 = i;
    ll max_val = l[i] - i, min_val = r[i] - i - 1;
    for (int bt = lim - 1; bt >= 0; --bt) {
      if (idx1 + (1 << bt) < n) {
        ll m1 = max_val;
        if (jump_max[idx1 + 1][bt] > m1)
          m1 = jump_max[idx1 + 1][bt];
        if (m1 <= t - i) {
          max_val = m1;
          idx1 += 1 << bt;
        }
      }
      if (idx2 + (1 << bt) < n) {
        ll m2 = min_val;
        if (jump_min[idx2 + 1][bt] < m2)
          m2 = jump_min[idx2 + 1][bt];
        if (t - i <= m2) {
          min_val = m2;
          idx2 += 1 << bt;
        }
      }
    }
    if (max_val <= t - i)
      idx1 = idx1 + 1 < n ? idx1 + 1 : n;
    if (t - i <= min_val)
      idx2 = idx2 + 1 < n ? idx2 + 1 : n;
    return {idx1, idx2};
  };

  std::vector jump(n + 1,
                   std::vector(2, std::vector<std::pair<int, int>>(lim)));
  std::vector cost(n + 1, std::vector(2, std::vector<ll>(lim)));
  // jump[{i, j}][bt] = {i, j}
  // cost[{i, j}][bt] = x
  // base cases for binary lift
  jump[n][0][0] = {n, 0}, jump[n][1][0] = {n, 1};
  for (int i = 0; i < n; ++i) {
    std::vector<ll> idx = {l[i], r[i] - 1};
    for (int j = 0; j < 2; ++j) {
      auto res = binary_search(i, idx[j]);
      if (res.first < res.second) {
        jump[i][j][0] = std::make_pair(res.first, 0LL);
      } else {
        jump[i][j][0] = std::make_pair(res.second, 1LL);
        cost[i][j][0] =
            std::max(0LL, idx[j] + (res.second - i) - (r[res.second] - 1));
      }
    }
  }
  for (int bt = 1; bt < lim; ++bt) {
    for (int i = 0; i <= n; ++i) {
      for (int j = 0; j < 2; ++j) {
        auto dest = jump[i][j][bt - 1];
        cost[i][j][bt] =
            cost[i][j][bt - 1] + cost[dest.first][dest.second][bt - 1];
        jump[i][j][bt] = jump[dest.first][dest.second][bt - 1];
      }
    }
  }
  auto bin_lift = [&](int i, int j,
                      int max_i) -> std::pair<std::pair<int, int>, ll> {
    ll ans = 0;
    for (int bt = lim - 1; bt >= 0; --bt) {
      if (i + (1 << bt) >= n) {
        continue;
      }
      if (jump[i][j][bt].first > max_i) {
        continue;
      }
      ans += cost[i][j][bt];
      auto dest = jump[i][j][bt];
      i = dest.first, j = dest.second;
    }
    return {{i, j}, ans};
  };

  for (auto &[a, b, c, d, i] : queries) {
    // process query
    ll cost = 0;
    auto res = binary_search(a, b);
    if (c <= std::min(res.first, res.second)) {
      b += c - a;
      cost += std::max(0LL, b - d);
      ans[i] = std::max(ans[i], cost);
      continue;
    }
    if (res.first < res.second) {
      b = l[res.first];
      auto [dest, cost_del] = bin_lift(res.first, 0, c - 1);
      cost += cost_del;
      b = dest.second == 0 ? l[dest.first] : r[dest.first] - 1;
      b += (c - 1) - dest.first;
      if (b > r[c - 1] - 1) {
        cost += b - (r[c - 1] - 1);
        b = r[c - 1] - 1;
      }
      cost += std::max(0LL, b + 1 - d);
    } else {
      b += res.second - a;
      if (b > r[res.second] - 1) {
        cost += b - (r[res.second] - 1);
        b = r[res.second] - 1;
      }
      auto [dest, cost_del] = bin_lift(res.second, 1, c - 1);
      cost += cost_del;
      b = dest.second == 0 ? l[dest.first] : r[dest.first] - 1;
      b += (c - 1) - dest.first;
      if (b > r[c - 1] - 1) {
        cost += b - (r[c - 1] - 1);
        b = r[c - 1] - 1;
      }
      cost += std::max(0LL, b + 1 - d);
    }
    ans[i] = std::max(ans[i], cost);
  }
}

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

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