Submission #925134

#	Time	Username	Problem	Language	Result	Execution time	Memory
925134		myst6	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	440 ms	232804 KiB

apple

#include <bits/stdc++.h>

using namespace std;

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

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int M;
  cin >> M;
  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, 1, 1'000'000'000);
      cout << count << "\n";
      C = count;
    } else {
      tree.update(X+C, Y+C, 1, 1'000'000'000);
    }
  }
  return 0;
}

• Subtask 1: 100 / 100