Submission #597769

#	Time	Username	Problem	Language	Result	Execution time	Memory
597769		Shreyan_Paliwal	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	18 ms	980 KiB

apple

// #include <bits/stdc++.h>

// #define FOR(i, x, y) for (int i = x; i < y; i++)

// typedef long long ll;
// using namespace std;

// struct Node {
//   int sum, lazy, tl, tr, l, r;
//   Node() : sum(0), lazy(0), l(-1), r(-1) {}
// };

// const int MAXN = 123456;
// Node      segtree[64 * MAXN];
// int       cnt = 2;

// void push_lazy(int node) {
//   if (segtree[node].lazy) {
//     segtree[node].sum = segtree[node].tr - segtree[node].tl + 1;
//     int mid           = (segtree[node].tl + segtree[node].tr) / 2;
//     if (segtree[node].l == -1) {
//       segtree[node].l             = cnt++;
//       segtree[segtree[node].l].tl = segtree[node].tl;
//       segtree[segtree[node].l].tr = mid;
//     }
//     if (segtree[node].r == -1) {
//       segtree[node].r             = cnt++;
//       segtree[segtree[node].r].tl = mid + 1;
//       segtree[segtree[node].r].tr = segtree[node].tr;
//     }
//     segtree[segtree[node].l].lazy = segtree[segtree[node].r].lazy = 1;
//     segtree[node].lazy                                            = 0;
//   }
// }

// void update(int node, int l, int r) {
//   push_lazy(node);
//   if (l == segtree[node].tl && r == segtree[node].tr) {
//     segtree[node].lazy = 1;
//     push_lazy(node);
//   } else {
//     int mid = (segtree[node].tl + segtree[node].tr) / 2;
//     if (segtree[node].l == -1) {
//       segtree[node].l             = cnt++;
//       segtree[segtree[node].l].tl = segtree[node].tl;
//       segtree[segtree[node].l].tr = mid;
//     }
//     if (segtree[node].r == -1) {
//       segtree[node].r             = cnt++;
//       segtree[segtree[node].r].tl = mid + 1;
//       segtree[segtree[node].r].tr = segtree[node].tr;
//     }

//     if (l > mid)
//       update(segtree[node].r, l, r);
//     else if (r <= mid)
//       update(segtree[node].l, l, r);
//     else {
//       update(segtree[node].l, l, mid);
//       update(segtree[node].r, mid + 1, r);
//     }

//     push_lazy(segtree[node].l);
//     push_lazy(segtree[node].r);
//     segtree[node].sum = segtree[segtree[node].l].sum + segtree[segtree[node].r].sum;
//   }
// }

// int query(int node, int l, int r) {
//   push_lazy(node);
//   if (l == segtree[node].tl && r == segtree[node].tr)
//     return segtree[node].sum;
//   else {
//     int mid = (segtree[node].tl + segtree[node].tr) / 2;
//     if (segtree[node].l == -1) {
//       segtree[node].l             = cnt++;
//       segtree[segtree[node].l].tl = segtree[node].tl;
//       segtree[segtree[node].l].tr = mid;
//     }
//     if (segtree[node].r == -1) {
//       segtree[node].r             = cnt++;
//       segtree[segtree[node].r].tl = mid + 1;
//       segtree[segtree[node].r].tr = segtree[node].tr;
//     }

//     if (l > mid)
//       return query(segtree[node].r, l, r);
//     else if (r <= mid)
//       return query(segtree[node].l, l, r);
//     else
//       return query(segtree[node].l, l, mid) + query(segtree[node].r, mid + 1, r);
//   }
// }

// int main() {
//   iostream::sync_with_stdio(false);
//   cin.tie(0);
//   int m;
//   cin >> m;

//   segtree[1].sum  = 0;
//   segtree[1].lazy = 0;
//   segtree[1].tl   = 1;
//   segtree[1].tr   = 1e9;

//   int c = 0;
//   for (int i= 0; i < m;) {
//     int d, x, y;
//     cin >> d >> x >> y;
//     if (d == 1) {
//       c = query(1, x + c, y + c);
//       cout << c << '\n';
//     } else
//       update(1, x + c, y + c);
//   }
//   return 0;
// }

#include <bits/stdc++.h>
using namespace std;

struct Node {
  int   v    = 0, l, r;
  Node* c[2] = { nullptr, nullptr };

  bool f() { return (v == (r - l + 1)); }

  Node* ML() {
    if (c[0]) return c[0];
    c[0]    = new Node;
    int m   = (l + r) >> 1;
    c[0]->l = l, c[0]->r = m;
    if (f()) c[0]->set();
    return c[0];
  }

  Node* MR() {
    if (c[1]) return c[1];
    c[1]    = new Node;
    int m   = (l + r) >> 1;
    c[1]->l = m + 1, c[1]->r = r;
    if (f()) c[1]->set();
    return c[1];
  }

  void set() { v = (r - l + 1); }

  int val(int k) { return (c[k] ? c[k]->v : 0); }

  void merge() { v = val(0) + val(1); }

  void push() {
    if (!f()) return;
    if (l != r) {
      if (c[0]) c[0]->set();
      if (c[1]) c[1]->set();
    }
  }

  void upd(int L, int R) {
    push();
    if (R < l || r < L) return;
    if (L <= l && r <= R) {
      set();
      return;
    }
    ML()->upd(L, R);
    MR()->upd(L, R);
    merge();
  }

  int qry(int L, int R) {
    push();
    if (R < l || r < L) return 0;
    if (L <= l && r <= R) return v;
    return ML()->qry(L, R) + MR()->qry(L, R);
  }
};

int n;

int main() {
  // freopen("main.in", "r", stdin);

  Node* seg = new Node;
  seg->l = 1, seg->r = 100000;

  cin >> n;

  int c = 0;
  for (int i = 0; i < n; i++) {
    int D, X, Y;
    cin >> D >> X >> Y;
    if (D == 2)
      seg->upd(X + c, Y + c);
    else {
      c = seg->qry(X + c, Y + c);
      cout << c << '\n';
    }
  }

  return 0;
}

• Subtask 1: 0 / 100