제출 #872326

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
872326		MilosMilutinovic	Bitaro, who Leaps through Time (JOI19_timeleap)	C++14	0 / 100	404 ms	524288 KiB

timeleap

#include <bits/stdc++.h>

using namespace std;

const int N = 300000;
const int inf = (int) 1e9;

struct node {
  int L, R, to;
  long long cost;
  node(int L = 0, int R = inf, int to = 0, long long cost = 0) : L(L), R(R), to(to), cost(cost) {}
} st[2][4 * N];

node merge(node l, node r) {
  if (l.to != inf) {
    return node(l.L, l.R, r.to != inf ? r.to : min(max(l.to, r.L), r.R), l.cost + r.cost + max(0, l.to - r.R));
  }
  if (l.R < r.L) {
    return node(l.R, l.R, r.to != inf ? r.to : r.L, l.cost + r.cost);
  }
  if (l.L > r.R) {
    return node(l.L, l.L, r.to != inf ? r.to : r.R, l.cost + r.cost + l.L - r.R);
  }
  return node(max(l.L, r.L), min(l.R, r.R), r.to != inf ? r.to : inf, l.cost + r.cost);
}

int n, q, from[2][N], to[2][N];

void Build(int t, int id, int l, int r) {
  if (l == r) {
    st[t][id] = node(from[t][l], to[t][l], inf, 0);
    return;
  }
  int mid = (l + r) / 2;
  Build(t, id << 1, l, mid);
  Build(t, id << 1 | 1, mid + 1, r);
  st[t][id] = merge(st[t][id << 1], st[t][id << 1 | 1]);
}

void Update(int t, int id, int l, int r, int p) {
  if (l == r) {
    st[t][id] = node(from[t][l], to[t][l], inf, 0);
    return;
  }
  int mid = (l + r) / 2;
  if (p <= mid) {
    Update(t, id << 1, l, mid, p);
  } else {
    Update(t, id << 1 | 1, mid + 1, r, p);
  }
  st[t][id] = merge(st[t][id << 1], st[t][id << 1 | 1]);
}

node Query(int t, int id, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) {
    return st[t][id];
  }
  int mid = (l + r) / 2;
  if (qr <= mid) {
    return Query(t, id << 1, l, mid, ql, qr);
  } else if (ql > mid) {
    return Query(t, id << 1 | 1, mid + 1, r, ql, qr);
  } else {
    return merge(Query(t, id << 1, l, mid, ql, qr), Query(t, id << 1 | 1, mid + 1, r, ql, qr));
  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> q;
  for (int i = 1; i < n; i++) {
    cin >> from[0][i] >> to[0][i];
    --to[0][i];
    from[1][n - i] = from[0][i];
    to[1][n - i] = to[0][i];
  }
  for (int i = 1; i < n; i++) {
    from[0][i] -= i;
    to[0][i] -= i;
    from[1][i] -= i;
    to[1][i] -= i;
  }
  Build(0, 1, 1, n - 1);
  Build(1, 1, 1, n - 1);
  while (q--) {
    int op;
    cin >> op;
    if (op == 1) {
      int p, s, e;
      cin >> p >> s >> e;
      --e;
      from[0][p] = s - p;
      to[0][p] = e - p;
      from[1][n - p] = s - (n - p);
      to[1][n - p] = e - (n - p);
      Update(0, 1, 1, n - 1, p);
      Update(1, 1, 1, n - 1, n - p);
    } else {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      if (a == c) {
        cout << max(b - d, 0) << '\n';
        continue;
      }
      int t = (a < c ? 0 : 1);
      if (a > c) {
        a = n - a + 1;
        c = n - c + 1;
      }
      b -= a;
      d -= c;
      node L = node(b, b, b, 0);
      node R = node(d, d, d, 0);
      node seg = Query(t, 1, 1, n - 1, a, c - 1);
      cout << merge(merge(L, seg), R).cost << '\n'; 
    }
  }
  return 0;
}

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