Submission #670055

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
670055	2022-12-08T01:19:53 Z	nhuang685	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	410 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	1 ms	212 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	18 ms	8840 KB	Output is correct
5	Correct	22 ms	10716 KB	Output is correct
6	Correct	23 ms	10352 KB	Output is correct
7	Correct	21 ms	10700 KB	Output is correct
8	Correct	182 ms	79100 KB	Output is correct
9	Correct	338 ms	131400 KB	Output is correct
10	Correct	360 ms	150768 KB	Output is correct
11	Correct	368 ms	163448 KB	Output is correct
12	Correct	380 ms	169120 KB	Output is correct
13	Correct	357 ms	207832 KB	Output is correct
14	Correct	365 ms	209996 KB	Output is correct
15	Runtime error	410 ms	262144 KB	Execution killed with signal 9
16	Halted	0 ms	0 KB	-