제출 #1193274

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1193274		lopkus	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	113 ms	31916 KiB

apple

#include <bits/stdc++.h>

#define int int64_t

const int N = 1e6 + 1;

struct seg {
  int t[N] = {0};
  int ll[N] = {0};
  int rr[N] = {0};
  int lazy[N] = {0};
  int timer = 2;
  void push(int v, int tl, int tr) {
    if(!lazy[v]) {
      return;
    }
    t[v] = tr - tl + 1;
    lazy[ll[v]] = 1;
    lazy[rr[v]] = 1;
    lazy[v] = 0;
  }
  void create(int v) {
    if(!ll[v]) {
      ll[v] = timer++;
    }
    if(!rr[v]) {
      rr[v] = timer++;
    }
  }
  int query(int v, int tl, int tr, int l, int r) {
    if(tl < tr)
      create(v);
    push(v, tl, tr);
    if(tl >= l && tr <= r) {
      return t[v];
    }
    if(tl > r || tr < l) {
      return 0;
    }
    int mid = (tl + tr) / 2;
    return query(ll[v], tl, mid, l, r) + query(rr[v], mid + 1, tr, l, r);
  }
  void update(int v, int tl, int tr, int l, int r) {
    if(tl != tr)
      create(v);
    push(v, tl, tr);
    if(tl >= l && tr <= r) {
      lazy[v] = 1;
      push(v, tl, tr);
      return;
    }
    if(tl > r || tr < l) {
      return;
    }
    int mid = (tl + tr) / 2;
    update(ll[v], tl, mid, l, r);
    update(rr[v], mid + 1, tr, l, r);
    t[v] = (t[ll[v]] + t[rr[v]]);
  }
}seg;

void solve() {
  int m;
  std::cin >> m;
  int prv = 0;
  while(m--) {
    int type;
    std::cin >> type;
    if(type == 2) {
      int l, r;
      std::cin >> l >> r;
      l += prv;
      r += prv;
      seg.update(1, 1, 1e9, l, r);
    }
    else {
      int l, r;
      std::cin >> l >> r;
      l += prv;
      r += prv;
      int ans = seg.query(1, 1, 1e9, l, r);
      std::cout << ans << "\n";
      prv = ans;
    }
  }
}


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

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 0 / 100