Submission #706871

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
706871	2023-03-08T02:22:39 Z	nhuang685	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	551 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:
  int 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, int l, int r) {
    assert(n != nullptr);
    if (l != r) {
      if (n->l == nullptr) n->l = new node();
      if (n->r == nullptr) n->r = new node();
    }

    if (n->lazy == ID2) return;
    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(int a, int b, T c, int l, int 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;
    }
    int mid = (l + r) / 2;
    set(a, b, c, l, mid, n->l);
    set(a, b, c, mid + 1, r, n->r);
    pull(n);
  }

  T query(int a, int b, int l, int 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;
    }
    int mid = (l + r) / 2;
    return comb(query(a, b, l, mid, n->l), query(a, b, mid + 1, r, n->r));
  }

 public:
  Seg() {}
  Seg(int _sz) {
    for (sz = 1; sz < _sz; sz *= 2)
      ;
    root = new node();
  }
  ~Seg() { delete root; }
  void set(int a, int b, T c) { set(a, b, c, 0, sz - 1, root); }
  T query(int a, int 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	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	17 ms	6092 KB	Output is correct
5	Correct	23 ms	7332 KB	Output is correct
6	Correct	20 ms	6988 KB	Output is correct
7	Correct	27 ms	7244 KB	Output is correct
8	Correct	149 ms	53708 KB	Output is correct
9	Correct	299 ms	89548 KB	Output is correct
10	Correct	316 ms	102528 KB	Output is correct
11	Correct	325 ms	110944 KB	Output is correct
12	Correct	345 ms	114652 KB	Output is correct
13	Correct	309 ms	140640 KB	Output is correct
14	Correct	333 ms	142000 KB	Output is correct
15	Correct	549 ms	257844 KB	Output is correct
16	Correct	543 ms	259844 KB	Output is correct
17	Correct	337 ms	147020 KB	Output is correct
18	Correct	333 ms	147156 KB	Output is correct
19	Runtime error	551 ms	262144 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-