Submission #410221

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410221	2021-05-22T09:52:58 Z	Alex_tz307	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	324 ms	141768 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)
    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	67 ms	141124 KB	Output is correct
2	Correct	66 ms	141252 KB	Output is correct
3	Correct	65 ms	141188 KB	Output is correct
4	Correct	76 ms	141124 KB	Output is correct
5	Correct	79 ms	141196 KB	Output is correct
6	Correct	79 ms	141196 KB	Output is correct
7	Correct	77 ms	141124 KB	Output is correct
8	Correct	166 ms	141356 KB	Output is correct
9	Correct	253 ms	141452 KB	Output is correct
10	Correct	262 ms	141480 KB	Output is correct
11	Correct	266 ms	141580 KB	Output is correct
12	Correct	267 ms	141636 KB	Output is correct
13	Correct	244 ms	141680 KB	Output is correct
14	Correct	243 ms	141624 KB	Output is correct
15	Correct	316 ms	141712 KB	Output is correct
16	Correct	314 ms	141644 KB	Output is correct
17	Correct	250 ms	141768 KB	Output is correct
18	Correct	249 ms	141636 KB	Output is correct
19	Correct	324 ms	141644 KB	Output is correct
20	Correct	320 ms	141624 KB	Output is correct