Submission #1185841

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

timeleap

#include <bits/stdc++.h>

typedef long long ll;

const ll inf = 1e15;

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

const int N = 3e5 + 1;
const int lim = 15;

ll l[N], r[N], ans[N], jump_min[N][lim], jump_max[N][lim];
std::pair<ll, ll> ansl[N][lim], ansr[N][lim];

int n, q;

std::pair<ll, ll> _ansl(int i, int x) {
  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};
}

std::pair<ll, ll> _ansr(int i, int x) {
  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::pair<ll, ll> _ans(int i, int x, ll t) {
  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) {
    ll m1 = std::max(max_val, jump_max[idx1 + 1][bt]),
       m2 = std::min(min_val, jump_min[idx2 + 1][bt]);
    if (idx1 + (1 << bt) < n and m1 <= t - i) {
      max_val = m1;
      idx1 += 1 << bt;
    }
    if (idx2 + (1 << bt) < n and t - i <= m2) {
      min_val = m2;
      idx2 += 1 << bt;
    }
  }
  if (max_val <= t - i) {
    idx1 = std::min(n, idx1 + 1);
  }
  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) {
    return _ansl(idx1, x - free_jumps);
  } else {
    auto p = _ansr(idx2, x - free_jumps);
    return {t + free_jumps - r[idx2] + p.first + 1, p.second};
  }
}

void solve(std::vector<Query> &queries) {
  for (int i = 0; i < n; ++i) {
    ll v1 = std::max(0LL, l[i] - r[i + 1] + 2);
    ll v2 = std::max(0LL, r[i] - r[i + 1] + 1);
    ansl[i][0] = {v1, l[i] - v1 + 1};
    ansr[i][0] = {v2, r[i] - v2};
    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 [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) {
    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;
    }
    if (++time > d) {
      cost += time - d;
    }
    ans[i] = std::max(ans[i], cost);
  }
}

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

  std::cin >> n >> q;
  l[n - 1] = inf, r[n - 1] = inf + 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) {
      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(q1);
  std::reverse(l, l + n - 1);
  std::reverse(r, r + n - 1);
  solve(q2);
  for (int i = 0; i < q; ++i) {
    std::cout << ans[i] << '\n';
  }
}

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