Submission #597762

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

apple

#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;

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

  return 0;
}

• Subtask 1: 0 / 100