Submission #1193297

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193297		lopkus	Monkey and Apple-trees (IZhO12_apple)	C++20	100 / 100	344 ms	260596 KiB

apple

#include <bits/stdc++.h>

#define int int64_t

const int N = 20 * 1e6 + 1;

int root = 0;

struct seg {
  int lazy[N] = {0};
  int t[N] = {0};
  int ll[N] = {0};
  int rr[N] = {0};
  int ath = 0;
  void push(int v, int tl, int tr) {
    if(!lazy[v]) {
      return;
    }
    t[v] = tr - tl + 1;
    if(tl != tr) {
      if(!ll[v]) {
        ll[v] = ++ath;
      }
      if(!rr[v]) {
        rr[v] = ++ath;
      }
      lazy[ll[v]] = lazy[rr[v]] = 1;
    }
    lazy[v] = 0;
  }
  int query(int &c, int tl, int tr, int l, int r) {
    if(!c) {
      c = ++ath;
    }
    push(c, tl, tr);
    if(tl >= l && tr <= r) {
      return t[c];
    }
    if(tl > r || tr < l) {
      return 0;
    }
    int mid = (tl + tr) / 2;
    return query(ll[c], tl, mid, l, r) + query(rr[c], mid + 1, tr, l, r);
  }
  void update(int &c, int tl, int tr, int l, int r) {
    if(!c) {
      c = ++ath;
    }
    push(c, tl, tr);
    if(tl >= l && tr <= r) {
      lazy[c] = 1;
      push(c, tl, tr);
      return;
    }
    if(tl > r || tr < l) {
      return;
    }
    int mid = (tl + tr) / 2;
    update(ll[c], tl, mid, l, r);
    update(rr[c], mid + 1, tr, l, r);
    t[c] = t[ll[c]] + t[rr[c]];
  }
}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(root, 1, 1e9, l, r);
    }
    else {
      int l, r;
      std::cin >> l >> r;
      l += prv;
      r += prv;
      int ans = seg.query(root, 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: 100 / 100