Submission #869303

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869303	2023-11-04T01:55:14 Z	nima_aryan	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	217 ms	184792 KB

apple

/**
 *    author:  NimaAryan
 *    created: 2023-11-04 02:46:41  
**/
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "algo/debug.h"
#endif

using i64 = long long;

template <class Info, class Tag>
class SparseLazySegmentTree {
 public:
  vector<Info> info;
  vector<Tag> tag;
  int n;

  struct Node {
    int left = -1, right = -1;
  };
  vector<Node> nodes;
  
  int num = 0;
  void make_childs(int p) {
    if (nodes[p].left == -1) {
      nodes[p].left = ++num;
    }
    if (nodes[p].right == -1) {
      nodes[p].right = ++num;
    }
  }

  SparseLazySegmentTree(int n, int q) : n(n) {
    int m = 2 * __lg(n) * q;
    info.resize(m), tag.resize(m);
    nodes.resize(m);
  }

  void pull(int p) {
    info[p] = info[nodes[p].left] + info[nodes[p].right];
  }
  void apply(int p, int l, int r, const Tag& v) {
    make_childs(p);
    info[p].apply(l, r, v);
    tag[p].apply(v);
  }
  void push(int p, int l, int r) {
    make_childs(p);
    int m = (l + r) / 2;
    apply(nodes[p].left, l, m, tag[p]);
    apply(nodes[p].right, m, r, tag[p]);
    tag[p] = Tag();
  }

  void modify(int p, int l, int r, int x, const Info& v) {
    make_childs(p);
    if (r - l == 1) {
      info[p] = v;
      return;
    }
    push(p, l, r);
    int m = (l + r) / 2;
    if (x < m) {
      modify(2 * p, l, m, x, v);
    } else {
      modify(2 * p + 1, m, r, x, v);
    }
    pull(p);
  }
  void modify(int x, const Info& v) {
    modify(0, 0, n, x, v);
  }

  void RangeApply(int p, int l, int r, int lx, int rx, const Tag& v) {
    make_childs(p);
    if (l >= rx || r <= lx) {
      return;
    }
    if (l >= lx && r <= rx) {
      apply(p, l, r, v);
      return;
    }
    push(p, l, r);
    int m = (l + r) / 2;
    RangeApply(nodes[p].left, l, m, lx, rx, v);
    RangeApply(nodes[p].right, m, r, lx, rx, v);
    pull(p);
  }
  void RangeApply(int lx, int rx, const Tag& v) {
    RangeApply(0, 0, n, lx, rx, v);
  }

  Info RangeQuery(int p, int l, int r, int lx, int rx) {
    make_childs(p);
    if (l >= rx || r <= lx) {
      return Info();
    }
    if (l >= lx && r <= rx) {
      return info[p];
    }
    push(p, l, r);
    int m = (l + r) / 2;
    return RangeQuery(nodes[p].left, l, m, lx, rx) +
           RangeQuery(nodes[p].right, m, r, lx, rx);
  }
  Info RangeQuery(int lx, int rx) {
    return RangeQuery(0, 0, n, lx, rx);
  }
};

struct Tag {
  int ripen = 0;

  void apply(const Tag& v) {
    ripen |= v.ripen;
  }
};
struct Info {
  int sum = 0;

  void apply(int l, int r, const Tag& v) {
    if (v.ripen) {
      sum = r - l;
    }
  }
};
Info operator+(const Info& a, const Info& b) {
  return Info{a.sum + b.sum};
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  constexpr int N = 1E9, A = 1E7;

  int M;
  cin >> M;
  SparseLazySegmentTree<Info, Tag> seg(N + 1, M);

  int C = 0;
  while (M--) {
    int D, X, Y;
    cin >> D >> X >> Y;
    X += C, Y += C;

    if (D == 1) {
      int res = seg.RangeQuery(X, Y + 1).sum;
      cout << (C = res) << "\n";
    } else {
      seg.RangeApply(X, Y + 1, Tag{1});
    }
  }

  return 0;
}

Compilation message

apple.cpp: In function 'int main()':
apple.cpp:139:26: warning: unused variable 'A' [-Wunused-variable]
  139 |   constexpr int N = 1E9, A = 1E7;
      |                          ^

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	11 ms	7772 KB	Output is correct
5	Correct	14 ms	9568 KB	Output is correct
6	Correct	14 ms	9560 KB	Output is correct
7	Correct	14 ms	9564 KB	Output is correct
8	Correct	102 ms	46192 KB	Output is correct
9	Correct	180 ms	91480 KB	Output is correct
10	Correct	180 ms	91476 KB	Output is correct
11	Correct	189 ms	91860 KB	Output is correct
12	Correct	210 ms	91476 KB	Output is correct
13	Correct	194 ms	91724 KB	Output is correct
14	Correct	179 ms	91676 KB	Output is correct
15	Runtime error	217 ms	184792 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-