Submission #670056

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670056	2022-12-08T01:20:38 Z	nhuang685	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	383 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<ll> 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	18 ms	8904 KB	Output is correct
5	Correct	21 ms	10700 KB	Output is correct
6	Correct	20 ms	10384 KB	Output is correct
7	Correct	21 ms	10680 KB	Output is correct
8	Correct	188 ms	79356 KB	Output is correct
9	Correct	330 ms	131520 KB	Output is correct
10	Correct	353 ms	150892 KB	Output is correct
11	Correct	373 ms	163692 KB	Output is correct
12	Correct	383 ms	169412 KB	Output is correct
13	Correct	346 ms	208020 KB	Output is correct
14	Correct	356 ms	209884 KB	Output is correct
15	Runtime error	376 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-