Submission #410227

#TimeUsernameProblemLanguageResultExecution timeMemory
410227Bomba_femeilor원숭이와 사과 나무 (IZhO12_apple)C++17
100 / 100
337 ms120476 KiB
    #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;
    }
#Verdict Execution timeMemoryGrader output
Fetching results...