Submission #925134

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
925134	2024-02-10T20:09:28 Z	myst6	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	440 ms	232804 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	12 ms	5212 KB	Output is correct
5	Correct	14 ms	6236 KB	Output is correct
6	Correct	14 ms	6192 KB	Output is correct
7	Correct	15 ms	6236 KB	Output is correct
8	Correct	114 ms	46416 KB	Output is correct
9	Correct	251 ms	79160 KB	Output is correct
10	Correct	275 ms	88740 KB	Output is correct
11	Correct	262 ms	95828 KB	Output is correct
12	Correct	301 ms	99100 KB	Output is correct
13	Correct	238 ms	121168 KB	Output is correct
14	Correct	249 ms	122624 KB	Output is correct
15	Correct	422 ms	225876 KB	Output is correct
16	Correct	440 ms	227664 KB	Output is correct
17	Correct	256 ms	129108 KB	Output is correct
18	Correct	246 ms	129108 KB	Output is correct
19	Correct	417 ms	232788 KB	Output is correct
20	Correct	417 ms	232804 KB	Output is correct