Submission #410224

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410224	2021-05-22T09:54:41 Z	Alex_tz307	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	321 ms	118248 KB

apple

#include <bits/stdc++.h>

using namespace std;

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

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

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	55 ms	117704 KB	Output is correct
2	Correct	55 ms	117712 KB	Output is correct
3	Correct	55 ms	117692 KB	Output is correct
4	Correct	65 ms	117712 KB	Output is correct
5	Correct	76 ms	117700 KB	Output is correct
6	Correct	67 ms	117764 KB	Output is correct
7	Correct	67 ms	117748 KB	Output is correct
8	Correct	147 ms	117828 KB	Output is correct
9	Correct	243 ms	118028 KB	Output is correct
10	Correct	249 ms	118092 KB	Output is correct
11	Correct	255 ms	118212 KB	Output is correct
12	Correct	259 ms	118096 KB	Output is correct
13	Correct	234 ms	118128 KB	Output is correct
14	Correct	244 ms	118156 KB	Output is correct
15	Correct	310 ms	118188 KB	Output is correct
16	Correct	312 ms	118084 KB	Output is correct
17	Correct	236 ms	118176 KB	Output is correct
18	Correct	239 ms	118248 KB	Output is correct
19	Correct	314 ms	118084 KB	Output is correct
20	Correct	321 ms	118084 KB	Output is correct