Submission #670065

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670065	2022-12-08T01:50:20 Z	nhuang685	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	547 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 (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(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;
    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;
    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	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	16 ms	5944 KB	Output is correct
5	Correct	20 ms	7212 KB	Output is correct
6	Correct	19 ms	6868 KB	Output is correct
7	Correct	19 ms	7124 KB	Output is correct
8	Correct	160 ms	52892 KB	Output is correct
9	Correct	306 ms	87952 KB	Output is correct
10	Correct	313 ms	100660 KB	Output is correct
11	Correct	333 ms	109224 KB	Output is correct
12	Correct	329 ms	112924 KB	Output is correct
13	Correct	322 ms	138700 KB	Output is correct
14	Correct	321 ms	139944 KB	Output is correct
15	Correct	519 ms	256160 KB	Output is correct
16	Correct	533 ms	258132 KB	Output is correct
17	Correct	316 ms	145228 KB	Output is correct
18	Correct	317 ms	145424 KB	Output is correct
19	Runtime error	547 ms	262144 KB	Execution killed with signal 9
20	Halted	0 ms	0 KB	-