Submission #1185797

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185797		avighna	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	0 / 100	2831 ms	302308 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);

  const 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 jump_min(n, std::vector<ll>(lim)),
      jump_max(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) {
        jump_min[i][bt] =
            std::min(jump_min[i][bt], jump_min[i + (1 << (bt - 1))][bt - 1]);
        jump_max[i][bt] =
            std::max(jump_max[i][bt], jump_max[i + (1 << (bt - 1))][bt - 1]);
      }
    }
  }
  auto _ans = [&](int i, int x, ll t) -> std::pair<ll, ll> {
    int idx1 = i;
    ll max_val = l[i] - i;
    for (int bt = lim - 1; bt >= 0; --bt) {
      if (idx1 + (1 << bt) >= n) {
        continue;
      }
      if (std::max(max_val, jump_max[idx1 + 1][bt]) <= t - i) {
        max_val = std::max(max_val, jump_max[idx1 + 1][bt]);
        idx1 += 1 << bt;
      }
    }
    if (max_val <= t - i) {
      idx1 = std::min(n, idx1 + 1);
    }
    int idx2 = i;
    ll min_val = r[i] - i - 1;
    for (int bt = lim - 1; bt >= 0; --bt) {
      if (idx2 + (1 << bt) >= n) {
        continue;
      }
      if (t - i <= std::min(min_val, jump_min[idx2 + 1][bt])) {
        min_val = std::min(min_val, jump_min[idx2 + 1][bt]);
        idx2 += 1 << bt;
      }
    }
    if (t - i <= min_val) {
      idx2 = std::min(n, idx2 + 1);
    }
    ll free_jumps = std::max(0, std::min(idx1, idx2) - i);
    if (x <= free_jumps) {
      ll del = std::max(0LL, t + x - (r[i + x] - 1));
      return {del, t + x - del};
    }
    if (idx1 < idx2) {
      auto p = _ansl(idx1, x - free_jumps);
      return p;
    } else {
      auto p = _ansr(idx2, x - free_jumps);
      return {t + free_jumps - (r[idx2] - 1) + p.first, p.second};
    }
  };
  for (int bt = 1; bt < lim; ++bt) {
    for (int i = 0; i + (1 << bt) < n; ++i) {
      auto [ans1, t1] =
          _ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansl[i][bt - 1].second);
      auto [ans2, t2] =
          _ans(i + (1 << (bt - 1)), 1 << (bt - 1), ansr[i][bt - 1].second);
      ansl[i][bt] = {ansl[i][bt - 1].first + ans1, t1};
      ansr[i][bt] = {ansr[i][bt - 1].first + ans2, t2};
    }
  }

  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] = std::max(ans[i], cost);
  }
  l.pop_back();
  r.pop_back();
}

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});
    }
  }
  std::vector<ll> ans(q);
  solve(n, q, l, r, q1, ans);
  // 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;
  // }
  // solve(n, q, l, r, q2, ans);
  for (auto &i : ans) {
    std::cout << i << '\n';
  }
}

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