Submission #410227

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
410227	2021-05-22T10:05:28 Z	Bomba_femeilor	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	337 ms	120476 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 = new node[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	57 ms	117700 KB	Output is correct
2	Correct	56 ms	117688 KB	Output is correct
3	Correct	57 ms	117700 KB	Output is correct
4	Correct	66 ms	117752 KB	Output is correct
5	Correct	69 ms	117908 KB	Output is correct
6	Correct	68 ms	117832 KB	Output is correct
7	Correct	68 ms	117872 KB	Output is correct
8	Correct	150 ms	118748 KB	Output is correct
9	Correct	262 ms	119924 KB	Output is correct
10	Correct	267 ms	119876 KB	Output is correct
11	Correct	276 ms	119908 KB	Output is correct
12	Correct	275 ms	119836 KB	Output is correct
13	Correct	255 ms	120188 KB	Output is correct
14	Correct	263 ms	120268 KB	Output is correct
15	Correct	328 ms	120408 KB	Output is correct
16	Correct	332 ms	120388 KB	Output is correct
17	Correct	255 ms	120336 KB	Output is correct
18	Correct	261 ms	120260 KB	Output is correct
19	Correct	337 ms	120476 KB	Output is correct
20	Correct	332 ms	120408 KB	Output is correct