Submission #410218

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410218	2021-05-22T09:42:29 Z	Alex_tz307	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	369 ms	141804 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) {
    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	79 ms	141272 KB	Output is correct
2	Correct	77 ms	141164 KB	Output is correct
3	Correct	77 ms	141124 KB	Output is correct
4	Correct	88 ms	141280 KB	Output is correct
5	Correct	95 ms	141348 KB	Output is correct
6	Correct	90 ms	141332 KB	Output is correct
7	Correct	89 ms	141332 KB	Output is correct
8	Correct	172 ms	141396 KB	Output is correct
9	Correct	297 ms	141668 KB	Output is correct
10	Correct	305 ms	141648 KB	Output is correct
11	Correct	299 ms	141700 KB	Output is correct
12	Correct	319 ms	141624 KB	Output is correct
13	Correct	289 ms	141804 KB	Output is correct
14	Correct	279 ms	141760 KB	Output is correct
15	Correct	365 ms	141792 KB	Output is correct
16	Correct	369 ms	141708 KB	Output is correct
17	Correct	274 ms	141736 KB	Output is correct
18	Correct	289 ms	141708 KB	Output is correct
19	Correct	358 ms	141700 KB	Output is correct
20	Correct	351 ms	141764 KB	Output is correct