Submission #1188572

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

timeleap

#include <bits/stdc++.h>

typedef long long ll;

const ll inf = 1e15;

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

template <typename T> class SegmentTree {
public:
  std::vector<T> seg;
  int n;
  T idt;
  std::function<T(T, T)> f = [](T a, T b) { return a + b; };

  SegmentTree(int n) : n(n), idt(0) { seg.resize(4 * n, idt); }
  SegmentTree(int n, const std::function<T(T, T)> &f, T idt)
      : n(n), idt(idt), f(f) {
    seg.resize(4 * n, idt);
  }

  T query(int v, int tl, int tr, int l, int r) {
    if (tl > tr or l > r or tr < l or r < tl) {
      return idt;
    }
    if (l <= tl and tr <= r) {
      return seg[v];
    }
    int tm = (tl + tr) / 2;
    return f(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
  }
  T query(int l, int r) { return query(1, 0, n, l, r); }

  void set(int v, int tl, int tr, int idx, T x) {
    if (tl > tr or idx < tl or idx > tr) {
      return;
    }
    if (tl == tr) {
      seg[v] = x;
      return;
    }
    int tm = (tl + tr) / 2;
    set(2 * v, tl, tm, idx, x);
    set(2 * v + 1, tm + 1, tr, idx, x);
    seg[v] = f(seg[2 * v], seg[2 * v + 1]);
  }
  void set(int idx, T x) { set(1, 0, n, idx, x); }

  // For a max segtree
  int first_greater(int v, int tl, int tr, int i, T x) {
    if (tr < i || seg[v] <= x) {
      return n;
    }

    if (tl == tr) {
      return tl;
    }

    int tm = (tl + tr) / 2;
    int res = first_greater(2 * v, tl, tm, i, x);
    if (res != n) {
      return res;
    }
    return first_greater(2 * v + 1, tm + 1, tr, i, x);
  }
  int first_greater(int i, T x) { return first_greater(1, 0, n, i, x); }

  // For a min segtree
  int first_less(int v, int tl, int tr, int i, T x) {
    if (tr < i || seg[v] >= x) {
      return n;
    }
    if (tl == tr) {
      return tl;
    }

    int tm = (tl + tr) / 2;
    int res = first_less(2 * v, tl, tm, i, x);
    if (res != n) {
      return res;
    }
    return first_less(2 * v + 1, tm + 1, tr, i, x);
  }
  int first_less(int i, T x) { return first_less(1, 0, n, i, x); }
};

void solve(int n, int q, std::vector<ll> l, std::vector<ll> r,
           std::vector<Query> queries, std::vector<ll> &ans) {
  SegmentTree<ll> max(n, [&](ll a, ll b) { return std::max(a, b); }, -inf);
  SegmentTree<ll> min(n, [&](ll a, ll b) { return std::min(a, b); }, inf);
  for (int i = 0; i < n; ++i) {
    max.set(i, l[i] - i);
    min.set(i, r[i] - i - 1);
  }
  auto binary_search = [&](int i, ll t) -> std::pair<ll, ll> {
    int idx1 = max.first_greater(i, t - i);
    int idx2 = min.first_less(i, t - i);
    return {idx1, idx2};
  };

  std::vector<int> jump(2 * n);
  std::vector<ll> cost(2 * n);
  const int block_sz = std::sqrt(2 * n);
  std::vector<int> jump_block(2 * n);
  std::vector<ll> cost_block(2 * n);
  // recalculates values for our block
  auto recalculate = [&](int idx) {
    int block_num = idx / block_sz;
    for (int i = std::min(2 * n, block_sz * (block_num + 1)) - 1;
         i >= block_sz * block_num; --i) {
      if (jump[i] >= std::min(2 * n, block_sz * (block_num + 1))) {
        jump_block[i] = jump[i];
        cost_block[i] = cost[i];
      } else {
        jump_block[i] = jump_block[jump[i]];
        cost_block[i] = cost_block[jump[i]] + cost[i];
      }
    }
  };
  // updates the values of jump and cost
  auto set_base_cases = [&](int i, std::vector<ll> idx) {
    for (int j = 0; j < 2; ++j) {
      auto res = binary_search(i, idx[j]);
      if (res.first < res.second) {
        jump[2 * i + j] = 2 * res.first;
        cost[2 * i + j] = 0;
      } else {
        jump[2 * i + j] = 2 * res.second + 1;
        cost[2 * i + j] =
            std::max(0LL, idx[j] + (res.second - i) - (r[res.second] - 1));
      }
      recalculate(2 * i + j);
    }
  };
  // base cases
  for (int i = 0; i < n; ++i) {
    set_base_cases(i, {l[i], r[i] - 1});
  }

  auto query = [&](int i, int max_i) -> std::pair<int, ll> {
    ll ans = 0;
    while (jump_block[i] / 2 <= max_i) {
      ans += cost_block[i];
      i = jump_block[i];
    }
    while (jump[i] / 2 <= max_i) {
      ans += cost[i];
      i = jump[i];
    }
    return {i, ans};
  };

  for (auto &[a, b, c, d, i, t] : queries) {
    // process query
    if (t == 1) {
      l[a] = b, r[a] = c;
      max.set(a, l[a] - a);
      min.set(a, r[a] - a - 1);
      set_base_cases(a, {l[a], r[a] - 1});
      for (int i = 0; i < n; ++i) {
        recalculate(2 * i);
        recalculate(2 * i + 1);
      }
    } else {
      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] = query(2 * res.first, c - 1);
        cost += cost_del;
        b = (dest & 1) == 0 ? l[(dest >> 1)] : r[(dest >> 1)] - 1;
        b += (c - 1) - (dest >> 1);
      } else {
        b += res.second - a;
        if (b > r[res.second] - 1) {
          cost += b - (r[res.second] - 1);
        }
        auto [dest, cost_del] = query(2 * res.second + 1, c - 1);
        cost += cost_del;
        b = (dest & 1) == 0 ? l[(dest >> 1)] : r[(dest >> 1)] - 1;
        b += (c - 1) - (dest >> 1);
      }
      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;
  int j = 0;
  for (int i = 0, t; i < q; ++i) {
    ll a, b, c, d;
    std::cin >> t;
    if (t == 1) {
      std::cin >> a >> b >> c;
      --a;
      q1.push_back({a, b, c, 0, 0, 1});
      q2.push_back({n - a - 1, b, c, 0, 0, 1});
    } else {
      std::cin >> a >> b >> c >> d;
      --a, --c;
      if (a == c) {
        ans[j++] = std::max(0LL, b - d);
        continue;
      }
      if (a < c) {
        q1.push_back({a, b, c, d, j, 2});
      } else {
        q2.push_back({n - a - 1, b, n - c - 1, d, j, 2});
      }
      j++;
    }
  }
  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 (int i = 0; i < j; ++i) {
    std::cout << ans[i] << '\n';
  }
}

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