Submission #1208559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208559		abczz	Bitaro, who Leaps through Time (JOI19_timeleap)	C++20	100 / 100	427 ms	91444 KiB

timeleap

#include <iostream>
#include <array>
#define ll long long

using namespace std;

ll n, q, ty, a, b, c, d;
array<ll, 2> R[300000];

array<ll, 2> nx(ll x, array<ll, 5> a) {
  if (a[2] == -1e18) return {min(max(x, a[0]), a[1]), max(0LL, x-a[1])};
  else return {a[2], max(0LL, x-a[1])+max(0LL, min(max(x, a[0]), a[1])-a[4])+a[3]};
}
array<ll, 5> merge(array<ll, 5> a, array<ll, 5> b) {
  if (a[2] == -1e18) {
    if (max(a[0], b[0]) <= min(a[1], b[1])) return {max(a[0], b[0]), min(a[1], b[1]), b[2], b[3], b[4]};
    else if (b[2] == -1e18) return {a[0], a[1], (a[1] < b[0] ? b[0] : b[1]), 0, (a[1] < b[0] ? b[0] : b[1])};
    else return {a[0], a[1], b[2], b[3]+max(0LL, (a[1] < b[0] ? b[0] : b[1])-b[4]), (a[1] < b[0] ? b[0] : b[1])};
  }
  else {
    auto u = nx(a[2], b);
    return {a[0], a[1], u[0], a[3]+u[1], a[4]};
  }
}

array<ll, 2> cur;

struct SegTree{
  array<ll, 5> st[1200000];
  void build(ll id, ll l, ll r, ll w) {
    if (l == r) {
      st[id] = {R[l][0] + w * l, R[l][1] + w * l, -(ll)1e18, 0, -(ll)1e18};
      return;
    }
    ll mid = (l+r)/2;
    build(id*2, l, mid, w);
    build(id*2+1, mid+1, r, w);
    if (w == -1) st[id] = merge(st[id*2], st[id*2+1]);
    else st[id] = merge(st[id*2+1], st[id*2]);
  }
  void update(ll id, ll l, ll r, ll q, ll x, ll y, ll w) {
    if (l == r) {
      st[id] = {x + w * l, y + w * l, -(ll)1e18, 0, -(ll)1e18};
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, x, y, w);
    else update(id*2+1, mid+1, r, q, x, y, w);
    if (w == -1) st[id] = merge(st[id*2], st[id*2+1]);
    else st[id] = merge(st[id*2+1], st[id*2]);
  }
  void query(ll id, ll l, ll r, ll ql, ll qr, ll w) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      auto u = nx(cur[0], st[id]);
      cur = {u[0], u[1]+cur[1]};
      return;
    }
    ll mid = (l+r)/2;
    if (w == -1) {
      query(id*2, l, mid, ql, qr, w);
      query(id*2+1, mid+1, r, ql, qr, w);
    }
    else {
      query(id*2+1, mid+1, r, ql, qr, w);
      query(id*2, l, mid, ql, qr, w);
    }
  }
}ST1, ST2;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  cin >> n >> q;
  for (int i=0; i<n-1; ++i) {
    cin >> R[i][0] >> R[i][1];
    --R[i][1];
  }
  if (n > 1) {
    ST1.build(1, 0, n-2, -1);
    ST2.build(1, 0, n-2, 1);
  }
  while (q--) {
    cin >> ty;
    if (ty == 1) {
      cin >> a >> b >> c;
      --a;
      ST1.update(1, 0, n-2, a, b, c-1, -1);
      ST2.update(1, 0, n-2, a, b, c-1, 1);
    }
    else {
      cin >> a >> b >> c >> d;
      --a, --c;
      if (a == c) cout << max(0LL, b-d) << '\n';
      else if (a < c) {
        cur = {b-a, 0};
        ST1.query(1, 0, n-2, a, c-1, -1);
        cur[0] += c;
        cout << cur[1] + max(0LL, cur[0]-d) << '\n';
      }
      else {
        cur = {b+a-1, 0};
        ST2.query(1, 0, n-2, c, a-1, 1);
        cur[0] -= c-1;
        cout << cur[1] + max(0LL, cur[0]-d) << '\n';
      }
    }
  }
}

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