Submission #706869

#	Time	Username	Problem	Language	Result	Execution time	Memory
706869		nhuang685	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	504 ms	262144 KiB

apple

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const ll DEFID2 = -1;
template <class T, T ID2 = DEFID2>
class Seg {
 private:
  size_t sz;
  T ID = 0;
  T comb(T i, T j) { return i + j; }
  struct node {
    T val, lazy;
    node *l, *r;
    node() : val(0), lazy(ID2) { l = r = nullptr; }
    node(T _val) : val(0), lazy(_val) { l = r = nullptr; }
  };
  node *root;

  void push(node *n, size_t l, size_t r) {
    assert(n != nullptr);
    if (n->lazy == ID2) return;
    if (l != r) {
      if (n->l == nullptr) n->l = new node();
      if (n->r == nullptr) n->r = new node();
    }

    n->val = (r - l + 1) * n->lazy;

    if (l != r) {
      n->l->lazy = n->lazy;
      n->r->lazy = n->lazy;
    }
    n->lazy = ID2;
  }
  void pull(node *n) { n->val = comb(n->l->val, n->r->val); }

  void set(size_t a, size_t b, T c, size_t l, size_t r, node *n) {
    assert(n != nullptr);
    push(n, l, r);

    if (b < l || r < a) return;
    if (a <= l && r <= b) {
      n->lazy = c;
      push(n, l, r);
      return;
    }
    size_t mid = (l + r) / 2;

    if (n->l == nullptr) n->l = new node();
    if (n->r == nullptr) n->r = new node();
    set(a, b, c, l, mid, n->l);
    set(a, b, c, mid + 1, r, n->r);
    pull(n);
  }

  T query(size_t a, size_t b, size_t l, size_t r, node *n) {
    assert(n != nullptr);
    push(n, l, r);

    if (b < l || r < a) return ID;
    if (a <= l && r <= b) {
      return n->val;
    }
    size_t mid = (l + r) / 2;

    if (n->l == nullptr) n->l = new node();
    if (n->r == nullptr) n->r = new node();
    return comb(query(a, b, l, mid, n->l), query(a, b, mid + 1, r, n->r));
  }

 public:
  Seg() {}
  Seg(size_t _sz) {
    for (sz = 1; sz < _sz; sz *= 2)
      ;
    root = new node();
  }
  void set(size_t a, size_t b, T c) { set(a, b, c, 0, sz - 1, root); }
  T query(size_t a, size_t b) { return query(a, b, 0, sz - 1, root); }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

#ifdef LOCAL
  // freopen("input.txt", "r", stdin);
  // freopen("output.txt", "w", stdout);
#endif

  Seg<int> seg((ll)1e9 + 1);

  int M;
  cin >> M;
  ll C = 0;
  while (M--) {
    int D;
    ll X, Y;
    cin >> D >> X >> Y;
    if (D == 1)
      cout << (C = seg.query(X + C, Y + C)) << '\n';
    else
      seg.set(X + C, Y + C, 1);
  }
}

• Subtask 1: 0 / 100