답안 #952334

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
952334 2024-03-23T14:31:51 Z ind1v 원숭이와 사과 나무 (IZhO12_apple) C++11
100 / 100
191 ms 189012 KB
#include <bits/stdc++.h>

using namespace std;

const int M = 1e5 + 5;
const int X = 1e9;

struct dynamic_segment_tree {
  struct node {
    int l, r, cnt;
    bool lz;
    
    node() : l(-1), r(-1), cnt(0), lz(false) {}
  } t[120 * M];
  int nd = 0, root;
  
  dynamic_segment_tree() {
    root = ++nd;
  }
  
  void create(int id) {
    if (t[id].l == -1) {
      t[id].l = ++nd;
    }
    if (t[id].r == -1) {
      t[id].r = ++nd;
    }
  }
  
  void push(int id, int tl, int tr) {
    int tm = (tl + tr) >> 1;
    t[t[id].l].cnt = tm - tl + 1;
    t[t[id].l].lz = t[id].lz;
    t[t[id].r].cnt = tr - tm;
    t[t[id].r].lz = t[id].lz;
    t[id].lz = false;
  }
  
  int get(int id, int tl, int tr, int l, int r) {
    if (l <= tl && tr <= r) {
      return t[id].cnt;
    }
    create(id);
    if (t[id].lz) {
      push(id, tl, tr);
    }
    int tm = (tl + tr) >> 1;
    if (r <= tm) {
      return get(t[id].l, tl, tm, l, r);
    } else if (tm + 1 <= l) {
      return get(t[id].r, tm + 1, tr, l, r);
    } else {
      return get(t[id].l, tl, tm, l, r) + get(t[id].r, tm + 1, tr, l, r);
    }
  }
  
  void upd(int id, int tl, int tr, int l, int r) {
    if (l <= tl && tr <= r) {
      t[id].cnt = tr - tl + 1;
      t[id].lz = true;
      return;
    }
    create(id);
    if (t[id].lz) {
      push(id, tl, tr);
    }
    int tm = (tl + tr) >> 1;
    if (r <= tm) {
      upd(t[id].l, tl, tm, l, r);
    } else if (tm + 1 <= l) {
      upd(t[id].r, tm + 1, tr, l, r);
    } else {
      upd(t[id].l, tl, tm, l, r);
      upd(t[id].r, tm + 1, tr, l, r);
    }
    t[id].cnt = t[t[id].l].cnt + t[t[id].r].cnt;
  }
} dst;

int m, c;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> m;
  while (m--) {
    int d, x, y;
    cin >> d >> x >> y;
    x += c; y += c;
    if (d == 1) {
      c = dst.get(1, 1, X, x, y);
      cout << c << '\n';
    } else if (d == 2) {
      dst.upd(1, 1, X, x, y);
    }
  }
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 95 ms 188244 KB Output is correct
2 Correct 37 ms 188240 KB Output is correct
3 Correct 35 ms 188212 KB Output is correct
4 Correct 44 ms 188244 KB Output is correct
5 Correct 42 ms 188312 KB Output is correct
6 Correct 42 ms 188280 KB Output is correct
7 Correct 41 ms 188348 KB Output is correct
8 Correct 74 ms 188500 KB Output is correct
9 Correct 121 ms 188596 KB Output is correct
10 Correct 132 ms 188496 KB Output is correct
11 Correct 127 ms 188568 KB Output is correct
12 Correct 169 ms 188500 KB Output is correct
13 Correct 119 ms 188752 KB Output is correct
14 Correct 126 ms 188576 KB Output is correct
15 Correct 165 ms 189012 KB Output is correct
16 Correct 156 ms 188756 KB Output is correct
17 Correct 146 ms 188732 KB Output is correct
18 Correct 119 ms 188612 KB Output is correct
19 Correct 191 ms 188720 KB Output is correct
20 Correct 151 ms 188568 KB Output is correct