Submission #706869

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
706869	2023-03-08T01:54:04 Z	nhuang685	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	504 ms	262144 KB

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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	328 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	16 ms	6004 KB	Output is correct
5	Correct	17 ms	7240 KB	Output is correct
6	Correct	17 ms	7080 KB	Output is correct
7	Correct	23 ms	7348 KB	Output is correct
8	Correct	137 ms	53732 KB	Output is correct
9	Correct	302 ms	89484 KB	Output is correct
10	Correct	309 ms	102588 KB	Output is correct
11	Correct	318 ms	110968 KB	Output is correct
12	Correct	310 ms	114608 KB	Output is correct
13	Correct	285 ms	140616 KB	Output is correct
14	Correct	312 ms	142028 KB	Output is correct
15	Correct	495 ms	257972 KB	Output is correct
16	Correct	504 ms	259848 KB	Output is correct
17	Correct	307 ms	146880 KB	Output is correct
18	Correct	291 ms	147112 KB	Output is correct
19	Runtime error	486 ms	262144 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-