Submission #410222

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410222	2021-05-22T09:53:54 Z	Alex_tz307	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	342 ms	118268 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	56 ms	117700 KB	Output is correct
2	Correct	56 ms	117656 KB	Output is correct
3	Correct	55 ms	117596 KB	Output is correct
4	Correct	65 ms	117708 KB	Output is correct
5	Correct	67 ms	117704 KB	Output is correct
6	Correct	66 ms	117660 KB	Output is correct
7	Correct	68 ms	117672 KB	Output is correct
8	Correct	147 ms	117912 KB	Output is correct
9	Correct	245 ms	118084 KB	Output is correct
10	Correct	250 ms	118064 KB	Output is correct
11	Correct	253 ms	118084 KB	Output is correct
12	Correct	254 ms	117980 KB	Output is correct
13	Correct	250 ms	118208 KB	Output is correct
14	Correct	239 ms	118268 KB	Output is correct
15	Correct	315 ms	118188 KB	Output is correct
16	Correct	308 ms	118108 KB	Output is correct
17	Correct	238 ms	118196 KB	Output is correct
18	Correct	238 ms	118180 KB	Output is correct
19	Correct	342 ms	118084 KB	Output is correct
20	Correct	313 ms	118136 KB	Output is correct