제출 #1043672

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1043672		juicy	Bitaro, who Leaps through Time (JOI19_timeleap)	C++17	0 / 100	287 ms	57708 KiB

timeleap

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 3e5 + 5;

struct Node {
  int s, t; long long c;

  Node(int s = 0, int t = 0, long long c = -1): s(s), t(t), c(c) {};

  friend Node operator + (const Node &lt, const Node &rt) {
    if (~lt.c && ~rt.c) {
      return {lt.s, rt.t, lt.c + rt.c + max(0, lt.t - rt.s)};
    }
    if (~lt.c) {
      return {lt.s, min(rt.t, max(lt.s, rt.s)), lt.c + max(0, lt.t - rt.t)};
    }
    if (~rt.c) {
      return {min(lt.t, max(lt.s, rt.s)), rt.t, max(0, lt.s - rt.s) + rt.c};
    }
    if (lt.t < rt.s) {
      return {lt.t, rt.s, 0};
    }
    if (lt.s > rt.t) {
      return {lt.s, rt.t, lt.s - rt.t};
    }
    return {max(lt.s, rt.s), min(lt.t, rt.t), -1};
  }
};

int n, q;

struct Segtree {
  Node s[4 * N];
  
  void upd(int i, int u, int v, int id = 1, int l = 1, int r = n - 1) {
    if (l == r) {
      s[id] = {u - i, v - i - 1};
      return;
    }
    int md = (l + r) / 2;
    if (i <= md) {
      upd(i, u, v, id * 2, l, md);
    } else {
      upd(i, u, v, id * 2 + 1, md + 1, r);
    }
    s[id] = s[id * 2] + s[id * 2 + 1];
  }

  Node qry(int u, int v, int id = 1, int l = 1, int r = n - 1) {
    if (u <= l && r <= v) {
      return s[id];
    }
    int md = (l + r) / 2;
    if (v <= md) {
      return qry(u, v, id * 2, l, md);
    }
    if (md < u) {
      return qry(u, v, id * 2 + 1, md + 1, r);
    }
    return qry(u, v, id * 2, l, md) + qry(u, v, id * 2 + 1, md + 1, r);
  }

  long long get(int l, int r, int s, int e) {
    if (l == r) {
      return max(0, s - e);
    }
    return max(0LL, (Node(s - l, s - l, -1) + qry(l, r - 1) + Node(e - r, e - r, -1)).c);
  }
} A, B;

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

  cin >> n >> q;
  for (int i = 1; i < n; ++i) {
    int l, r; cin >> l >> r;
    A.upd(i, l, r);
    B.upd(n - i, l, r);
  }
  while (q--) {
    int type; cin >> type;
    if (type == 1) {
      int p, s, e; cin >> p >> s >> e;
      A.upd(p, s, e);
      B.upd(n - p, s, e);
    } else {
      int s, e, l, r; cin >> l >> s >> r >> e;
      if (l <= r) {
        cout << A.get(l, r, s, e) << "\n";
      } else {
        cout << B.get(n - l + 1, n - r + 1, s, e) << "\n";
      }
    }
  }
  return 0;
}

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