Submission #925133

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925133	2024-02-10T20:06:31 Z	myst6	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	16 ms	9444 KB

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 = 0, qr = 0;
      ql = left->query(l, min(r, xm));
      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;
    }
  }
};

Node tree(1, 1'000'000);

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);
      cout << count << "\n";
      C = count;
    } else {
      tree.update(X+C, Y+C);
    }
  }
  return 0;
}

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	12 ms	7836 KB	Output is correct
5	Correct	15 ms	9444 KB	Output is correct
6	Correct	16 ms	9192 KB	Output is correct
7	Correct	15 ms	9308 KB	Output is correct
8	Runtime error	1 ms	344 KB	Execution killed with signal 11
9	Halted	0 ms	0 KB	-