Submission #925130

#	Time	Username	Problem	Language	Result	Execution time	Memory
925130		myst6	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	377 ms	262144 KiB

apple

#include <bits/stdc++.h>

using namespace std;

struct Node {
  bool tag;
  int xl, xr, sum;
  Node *left, *right;
  Node(int L, int R) : tag(false), xl(L), xr(R), sum(0), left(nullptr), right(nullptr) {}
  void extend() {
    if (xl != xr && !left) {
      int xm = (xl + xr) / 2;
      left = new Node(xl, xm);
      right = new Node(xm+1, xr);
    }
  }
  void apply() {
    extend();
    if (tag) {
      sum = xr - xl + 1;
      if (left) left->tag = true;
      if (right) right->tag = true;
      tag = false;
    }
  }
  int query(int l, int r) {
    if (l > r) return 0;
    apply();
    if (l == xl && r == xr) {
      return sum;
    } else {
      int xm = (xl + xr) / 2;
      int ql = left->query(l, min(r, xm));
      int qr = right->query(max(l, xm+1), r);
      return ql + qr;
    }
  }
  void update(int l, int r) {
    if (l > r) return;
    apply();
    if (l == xl && r == xr) {
      tag = true;
    } else {
      int xm = (xl + xr) / 2;
      left->update(l, min(r, xm));
      right->update(max(l, xm+1), r);
      left->apply(); right->apply();
      sum = left->sum + right->sum;
    }
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int M;
  cin >> M;
  Node tree(1, 1'000'000'000);
  int C = 0;
  for (int i=0; i<M; i++) {
    int D, X, Y;
    cin >> D >> X >> Y;
    if (D == 1) {
      int count = tree.query(X+C, Y+C);
      cout << count << "\n";
      C = count;
    } else {
      tree.update(X+C, Y+C);
    }
  }
  return 0;
}

• Subtask 1: 0 / 100