답안 #925130

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
925130 2024-02-10T19:54:08 Z myst6 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
377 ms 262144 KB
#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;
}
# 결과 실행 시간 메모리 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 -