Submission #410229

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410229	2021-05-22T10:12:24 Z	Alex_tz307	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	462 ms	206032 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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	1 ms	204 KB	Output is correct
3	Correct	1 ms	312 KB	Output is correct
4	Correct	15 ms	4944 KB	Output is correct
5	Correct	20 ms	5960 KB	Output is correct
6	Correct	17 ms	5708 KB	Output is correct
7	Correct	22 ms	5956 KB	Output is correct
8	Correct	135 ms	43876 KB	Output is correct
9	Correct	271 ms	75628 KB	Output is correct
10	Correct	289 ms	83792 KB	Output is correct
11	Correct	296 ms	89936 KB	Output is correct
12	Correct	297 ms	92888 KB	Output is correct
13	Correct	269 ms	108084 KB	Output is correct
14	Correct	287 ms	109064 KB	Output is correct
15	Correct	458 ms	199748 KB	Output is correct
16	Correct	443 ms	201116 KB	Output is correct
17	Correct	280 ms	112976 KB	Output is correct
18	Correct	297 ms	113108 KB	Output is correct
19	Correct	449 ms	205796 KB	Output is correct
20	Correct	462 ms	206032 KB	Output is correct