Submission #1188623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188623		avighna	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	100 / 100	382 ms	59508 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;
  std::function<T(T, T)> f = [](T a, T b) { return a + b; };
  T idt;

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

  void set(int idx, T x) {
    seg[idx += n] = x;
    for (idx /= 2; idx > 0; idx /= 2) {
      seg[idx] = f(seg[2 * idx], seg[2 * idx + 1]);
    }
  }

  T query(int l, int r) {
    T ansL = idt, ansR = idt;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) {
        ansL = f(ansL, seg[l++]);
      }
      if (r & 1) {
        ansR = f(seg[--r], ansR);
      }
    }
    return f(ansL, ansR);
  }
};

void solve(int n, int q, std::vector<ll> l, std::vector<ll> r,
           std::vector<Query> queries, std::vector<ll> &ans) {
  for (int i = 0; i < n - 1; ++i) {
    l[i] -= i, r[i] -= i + 1;
  }
  struct Function {
    bool type;
    ll l,
        r; // boundaries if type A, l is wavy func and r is forced exit if type
           // B
    ll k;  // delta if type B

    std::pair<ll, ll> operator()(ll t) {
      if (!type) {
        // type A
        if (t <= l) {
          return {l, 0};
        } else if (t <= r) {
          return {t, 0};
        } else {
          return {r, t - r};
        }
      } else {
        // type B
        if (t <= l) {
          return {r, k};
        } else {
          return {r, t - l + k};
        }
      }
    }
  };

  auto f = [&](Function x, Function y) -> Function {
    if (!x.type and !y.type) {
      // A + A
      ll l = std::max(x.l, y.l), r = std::min(x.r, y.r);
      if (l <= r) {
        return {0, l, r, 0};
      } else {
        if (x.l > y.r) {
          return {1, x.l, y.r, x.l - y.r};
        } else {
          return {1, x.r, y.l, 0};
        }
      }
    } else if (!x.type and y.type) {
      // A + B
      ll l = x.l, r = std::min(x.r, y.l);
      if (l <= r) {
        return {1, r, y.r, y.k};
      } else {
        return {1, l, y.r, y.k + l - r};
      }
    } else if (x.type and !y.type) {
      // B + A
      auto [t, c] = y(x.r);
      return {1, x.l, t, x.k + c};
    } else {
      // B + B
      auto [t, c] = y(x.r);
      return {1, x.l, t, x.k + c};
    }
  };
  SegmentTree<Function> tree(n - 1, f, {0, -inf, inf, 0});
  for (int i = 0; i < n - 1; ++i) {
    tree.set(i, {0, l[i], r[i], 0});
  }
  for (auto &[a, b, c, d, i, t] : queries) {
    if (t == 1) {
      tree.set(a, {0, b - a, c - a - 1, 0});
    } else {
      b -= a, d -= c;
      auto [time, cost] = tree.query(a, c - 1)(b);
      ans[i] = std::max(ans[i], cost + std::max(0LL, time - d));
    }
  }
}

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<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 - 2, 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());
  std::reverse(r.begin(), r.end());
  solve(n, q, l, r, q2, ans);
  for (int i = 0; i < j; ++i) {
    std::cout << ans[i] << '\n';
  }
}

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