제출 #410229

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
410229		Alex_tz307	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	462 ms	206032 KiB

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 / 100