답안 #410223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410223	2021-05-22T09:54:20 Z	Alex_tz307	원숭이와 사과 나무 (IZhO12_apple)	C++17	0 / 100	372 ms	191272 KB

apple

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5;
const int LOG = 40;

struct node {
  int sum, l, r, lSon, rSon;
  bool lazy_set;
  node() : sum(0), lSon(-1), rSon(-1), lazy_set(false) {}
} tree[MAXN * LOG];

int nodes = 1;

void add_left(int x) {
  int mid = (tree[x].l + tree[x].r) >> 1;
  if (tree[x].lSon == -1) {
    tree[x].lSon = ++nodes;
    tree[nodes].l = tree[x].l;
    tree[nodes].r = mid;
  }
}

void add_right(int x) {
  int mid = (tree[x].l + tree[x].r) >> 1;
  if (tree[x].rSon == -1) {
    tree[x].rSon = ++nodes;
    tree[nodes].l = mid + 1;
    tree[nodes].r = tree[x].r;
  }
}

void propagate(int x) {
  if (!tree[x].lazy_set)
    return;
  add_left(x);
  int son = tree[x].lSon;
  int n = tree[son].r - tree[son].l + 1;
  if (tree[son].sum < n) {
    tree[son].sum = n;
    tree[son].lazy_set = true;
  }
  add_right(x);
  son = tree[x].rSon;
  n = tree[son].r - tree[son].l + 1;
  if (tree[son].sum < n) {
    tree[son].sum = n;
    tree[son].lazy_set = true;
  }
  tree[x].lazy_set = false;
}

void update_sum(int x) {
  tree[x].sum = 0;
  if (tree[x].lSon != -1)
    tree[x].sum += tree[tree[x].lSon].sum;
  if (tree[x].rSon != -1)
    tree[x].sum += tree[tree[x].rSon].sum;
}

void range_set(int x, int st, int dr) {
  if (st <= tree[x].l && tree[x].r <= dr) {
    int n = tree[x].r - tree[x].l + 1;
    if (tree[x].sum == n)
      return;
    tree[x].sum = n;
    tree[x].lazy_set = true;
    return;
  }
  propagate(x);
  int mid = (tree[x].l + tree[x].r) >> 1;
  if (st <= mid) {
    add_left(x);
    range_set(tree[x].lSon, st, dr);
  }
  if (mid < dr) {
    add_right(x);
    range_set(tree[x].rSon, st, dr);
  }
  update_sum(x);
}

int query(int x, int st, int dr) {
  if (st <= tree[x].l && tree[x].r <= dr)
    return tree[x].sum;
  propagate(x);
  int mid = (tree[x].l + tree[x].r) >> 1, ans = 0;
  if (st <= mid && tree[x].lSon != -1)
    ans += query(tree[x].lSon, st, dr);
  if (mid < dr && tree[x].rSon != -1)
    ans += query(tree[x].rSon, st, dr);
  return ans;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int N;
  cin >> N;
  tree[1].sum = 0;
  tree[1].l = 1;
  tree[1].r = 1e9;
  int C = 0;
  for (int i = 0; i < N; ++i) {
    int t, l, r;
    cin >> t >> l >> r;
    l += C, r += C;
    if (t == 1) {
      C = query(1, l, r);
      cout << C << '\n';
    } else range_set(1, l, r);
  }
  return 0;
}

Subtask #1

0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	94148 KB	Output is correct
2	Correct	48 ms	94124 KB	Output is correct
3	Correct	44 ms	94164 KB	Output is correct
4	Correct	54 ms	94168 KB	Output is correct
5	Correct	57 ms	94228 KB	Output is correct
6	Correct	56 ms	94148 KB	Output is correct
7	Correct	57 ms	94260 KB	Output is correct
8	Correct	134 ms	94336 KB	Output is correct
9	Correct	236 ms	94572 KB	Output is correct
10	Correct	258 ms	94608 KB	Output is correct
11	Correct	247 ms	94572 KB	Output is correct
12	Correct	248 ms	94524 KB	Output is correct
13	Correct	225 ms	94652 KB	Output is correct
14	Correct	226 ms	94728 KB	Output is correct
15	Runtime error	372 ms	191272 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-