Submission #1341137

#TimeUsernameProblemLanguageResultExecution timeMemory
1341137vjudge1Monkey and Apple-trees (IZhO12_apple)C++20
100 / 100
218 ms137356 KiB
#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define el "\n"

class DynamicLazySegTree {
private:
  struct Node {
    int sum = 0;
    bool lazy = false;
    int lc = 0;
    int rc = 0;
  };

  vector<Node> tree;
  int n;

  inline int new_node() {
    int id = tree.size();
    tree.emplace_back();
    return id;
  }

  inline void apply(int p, int l, int r) {
    tree[p].lazy = true;
    tree[p].sum = r - l + 1;
  }

  inline void push(int p, int l, int r) {
    if (tree[p].lazy) {
      int mid = l + (r - l) / 2;
      if (!tree[p].lc) tree[p].lc = new_node();
      if (!tree[p].rc) tree[p].rc = new_node();
      apply(tree[p].lc, l, mid);
      apply(tree[p].rc, mid + 1, r);
      tree[p].lazy = false;
    }
  }

  inline void pull(int p) {
    int lsum = tree[p].lc ? tree[tree[p].lc].sum : 0;
    int rsum = tree[p].rc ? tree[tree[p].rc].sum : 0;
    tree[p].sum = lsum + rsum;
  }

  void set(int p, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr) {
      apply(p, l, r);
      return;
    }
    push(p, l, r);
    int mid = l + (r - l) / 2;
    if (ql <= mid) {
      if (!tree[p].lc) tree[p].lc = new_node();
      set(tree[p].lc, l, mid, ql, qr);
    }
    if (qr > mid) {
      if (!tree[p].rc) tree[p].rc = new_node();
      set(tree[p].rc, mid + 1, r, ql, qr);
    }
    pull(p);
  }

  int qry(int p, int l, int r, int ql, int qr) {
    if (ql > r || qr < l || p == 0) return 0;
    if (ql <= l && r <= qr) return tree[p].sum;
    push(p, l, r);
    int mid = l + (r - l) / 2;
    return qry(tree[p].lc, l, mid, ql, qr) + qry(tree[p].rc, mid + 1, r, ql, qr);
  }

public:
  DynamicLazySegTree(int _n, int max_nodes = 6000005) : n(_n) {
    tree.reserve(max_nodes);
    tree.emplace_back();
    tree.emplace_back();
  }

  void set(int ql, int qr) {
    if (ql > qr) return;
    set(1, 0, n - 1, ql, qr);
  }

  int qry(int ql, int qr) {
    if (ql > qr) return 0;
    return qry(1, 0, n - 1, ql, qr);
  }
};

void run_case(int tc) {
  int m;
  cin >> m;
  DynamicLazySegTree st(2000000005, 6000005);
  int c = 0;
  for (int i = 0; i < m; i++) {
    int d, x, y;
    cin >> d >> x >> y;
    int l = x + c - 1;
    int r = y + c - 1;
    if (d == 1) {
      c = st.qry(l, r);
      cout << c << el;
    } else if (d == 2) {
      st.set(l, r);
    }
  }
}

int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int _t = 1;
  // cin >> _t;
  for (int i = 1; i <= _t; i++) {
    run_case(i);
  }
  return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...