Submission #1193283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193283		lopkus	Monkey and Apple-trees (IZhO12_apple)	C++20	0 / 100	84 ms	31812 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 create(int v) {
    if (!ll[v]) ll[v] = timer++;
    if (!rr[v]) rr[v] = timer++;
  }

  void push(int v, int tl, int tr) {
    if (!lazy[v]) return;
    t[v] = tr - tl + 1;
    if (tl != tr) {
      create(v);
      lazy[ll[v]] = 1;
      lazy[rr[v]] = 1;
    }
    lazy[v] = 0;
  }

  int query(int v, int tl, int tr, int l, int r) {
    if(tl < tr) {
      create(v);
    }
    push(v, tl, tr);
    if (tl > r || tr < l) return 0;
    if (l <= tl && tr <= r) return t[v];
    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 > r || tr < l) return;
    if (l <= tl && tr <= r) {
      lazy[v] = 1;
      push(v, tl, tr);
      return;
    }
    if(tl < tr) {
      create(v);
    }
    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