제출 #1341143

#제출 시각아이디문제언어결과실행 시간메모리
1341143vjudge1원숭이와 사과 나무 (IZhO12_apple)C++20
100 / 100
221 ms137368 KiB
#include <bits/stdc++.h>

using namespace std;

#define int int64_t
#define el "\n"

struct Tag {
  int set_val = -1;

  inline bool has_update() const {
    return set_val != -1;
  }

  inline void apply(const Tag& t) {
    if (t.has_update()) {
      set_val = t.set_val;
    }
  }

  inline void clear() {
    set_val = -1;
  }
};

struct Info {
  int sum = 0;

  Info operator+(const Info& b) const {
    return {sum + b.sum};
  }

  inline void apply(const Tag& t, int l, int r) {
    if (t.has_update()) {
      sum = t.set_val * (r - l + 1);
    }
  }
};

template <class Info, class Tag>
class DynamicLazySegTree {
private:
  struct Node {
    Info info;
    Tag tag;
    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, const Tag& v, int l, int r) {
    tree[p].info.apply(v, l, r);
    tree[p].tag.apply(v);
  }

  inline void push(int p, int l, int r) {
    if (tree[p].tag.has_update()) {
      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, tree[p].tag, l, mid);
      apply(tree[p].rc, tree[p].tag, mid + 1, r);
      tree[p].tag.clear();
    }
  }

  inline void pull(int p) {
    Info l_info = tree[p].lc ? tree[tree[p].lc].info : Info();
    Info r_info = tree[p].rc ? tree[tree[p].rc].info : Info();
    tree[p].info = l_info + r_info;
  }

  void modify_impl(int p, int l, int r, int ql, int qr, const Tag& v) {
    if (ql > r || qr < l) return;
    if (ql <= l && r <= qr) {
      apply(p, v, 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();
      modify_impl(tree[p].lc, l, mid, ql, qr, v);
    }
    if (qr > mid) {
      if (!tree[p].rc) tree[p].rc = new_node();
      modify_impl(tree[p].rc, mid + 1, r, ql, qr, v);
    }
    pull(p);
  }

  Info query_impl(int p, int l, int r, int ql, int qr) {
    if (ql > r || qr < l || p == 0) return Info();
    if (ql <= l && r <= qr) return tree[p].info;
    push(p, l, r);
    int mid = l + (r - l) / 2;
    return query_impl(tree[p].lc, l, mid, ql, qr) +query_impl(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 modify(int ql, int qr, const Tag& v) {
    if (ql > qr) return;
    modify_impl(1, 0, n - 1, ql, qr, v);
  }

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

void run_case(int tc) {
  int m;
  cin >> m;
  DynamicLazySegTree<Info, Tag> 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.query(l, r).sum;
      cout << c << el;
    } else if (d == 2) {
      st.modify(l, r, {1});
    }
  }
}

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...