답안 #410220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410220	2021-05-22T09:51:24 Z	Alex_tz307	원숭이와 사과 나무 (IZhO12_apple)	C++17	100 / 100	497 ms	205544 KB

apple

#include <bits/stdc++.h>

using namespace std;

struct node {
  int sum, l, r;
  node *lSon, *rSon;
  bool lazy_set;
  node() : sum(0), lSon(nullptr), rSon(nullptr), lazy_set(false) {}
};

void add_left(node *&x) {
  int mid = (x->l + x->r) >> 1;
  if (x->lSon == nullptr) {
    x->lSon = new node();
    x->lSon->l = x->l;
    x->lSon->r = mid;
  }
}

void add_right(node *&x) {
  int mid = (x->l + x->r) >> 1;
  if (x->rSon == nullptr) {
    x->rSon = new node();
    x->rSon->l = mid + 1;
    x->rSon->r = x->r;
  }
}

void propagate(node *&x) {
  if (!x->lazy_set)
    return;
  add_left(x);
  int n = x->lSon->r - x->lSon->l + 1;
  if (x->lSon->sum < n) {
    x->lSon->sum = n;
    x->lSon->lazy_set = true;
  }
  add_right(x);
  n = x->rSon->r - x->rSon->l + 1;
  if (x->rSon->sum < n) {
    x->rSon->sum = n;
    x->rSon->lazy_set = true;
  }
  x->lazy_set = false;
}

void update_sum(node *&x) {
  x->sum = 0;
  if (x->lSon)
    x->sum += x->lSon->sum;
  if (x->rSon)
    x->sum += x->rSon->sum;
}

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

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int N;
  cin >> N;
  node *tree = new node();
  tree->l = 1;
  tree->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(tree, l, r);
      cout << C << '\n';
    } else range_set(tree, l, r);
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	204 KB	Output is correct
4	Correct	16 ms	4812 KB	Output is correct
5	Correct	19 ms	5772 KB	Output is correct
6	Correct	19 ms	5660 KB	Output is correct
7	Correct	20 ms	5872 KB	Output is correct
8	Correct	143 ms	43708 KB	Output is correct
9	Correct	288 ms	75592 KB	Output is correct
10	Correct	303 ms	83520 KB	Output is correct
11	Correct	313 ms	89932 KB	Output is correct
12	Correct	322 ms	92664 KB	Output is correct
13	Correct	301 ms	107844 KB	Output is correct
14	Correct	304 ms	108924 KB	Output is correct
15	Correct	487 ms	199584 KB	Output is correct
16	Correct	489 ms	200964 KB	Output is correct
17	Correct	308 ms	112776 KB	Output is correct
18	Correct	304 ms	112768 KB	Output is correct
19	Correct	497 ms	205544 KB	Output is correct
20	Correct	497 ms	205536 KB	Output is correct