Submission #410213

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410213	2021-05-22T09:37:58 Z	Alex_tz307	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	351 ms	143880 KB

apple

#include <bits/stdc++.h>

using namespace std;

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

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) {
    add_left(x);
    int son = tree[x].lSon;
    tree[son].sum = (tree[son].r - tree[son].l + 1) * tree[x].lazy_set;
    tree[son].lazy_set = tree[x].lazy_set;
    add_right(x);
    son = tree[x].rSon;
    tree[son].sum = (tree[son].r - tree[son].l + 1) * tree[x].lazy_set;
    tree[son].lazy_set = tree[x].lazy_set;
    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) {
    if (tree[x].sum == tree[x].r - tree[x].l + 1)
      return;
    tree[x].sum = tree[x].r - tree[x].l + 1;
    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) {
    add_left(x);
    ans += query(tree[x].lSon, st, dr);
  }
  if (mid < dr) {
    add_right(x);
    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	67 ms	141068 KB	Output is correct
2	Correct	68 ms	141076 KB	Output is correct
3	Correct	68 ms	141196 KB	Output is correct
4	Correct	79 ms	141344 KB	Output is correct
5	Correct	82 ms	141380 KB	Output is correct
6	Correct	82 ms	141592 KB	Output is correct
7	Correct	81 ms	141384 KB	Output is correct
8	Correct	172 ms	142128 KB	Output is correct
9	Correct	273 ms	143284 KB	Output is correct
10	Correct	288 ms	143316 KB	Output is correct
11	Correct	284 ms	143324 KB	Output is correct
12	Correct	292 ms	143360 KB	Output is correct
13	Correct	263 ms	143668 KB	Output is correct
14	Correct	268 ms	143688 KB	Output is correct
15	Correct	331 ms	143748 KB	Output is correct
16	Correct	338 ms	143880 KB	Output is correct
17	Correct	263 ms	143648 KB	Output is correct
18	Correct	298 ms	143772 KB	Output is correct
19	Correct	332 ms	143748 KB	Output is correct
20	Correct	351 ms	143860 KB	Output is correct