Submission #925130

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925130	2024-02-10T19:54:08 Z	myst6	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	377 ms	262144 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 = 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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	13 ms	7772 KB	Output is correct
5	Correct	15 ms	9548 KB	Output is correct
6	Correct	15 ms	9308 KB	Output is correct
7	Correct	16 ms	9564 KB	Output is correct
8	Correct	150 ms	70244 KB	Output is correct
9	Correct	276 ms	120360 KB	Output is correct
10	Correct	315 ms	134324 KB	Output is correct
11	Correct	301 ms	145444 KB	Output is correct
12	Correct	306 ms	150100 KB	Output is correct
13	Correct	284 ms	183296 KB	Output is correct
14	Correct	284 ms	185652 KB	Output is correct
15	Runtime error	377 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-