Submission #869304

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869304	2023-11-04T01:56:37 Z	nima_aryan	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	250 ms	182608 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 = 4 * __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;

  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;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	13 ms	15012 KB	Output is correct
5	Correct	16 ms	18524 KB	Output is correct
6	Correct	15 ms	18520 KB	Output is correct
7	Correct	15 ms	18652 KB	Output is correct
8	Correct	89 ms	91228 KB	Output is correct
9	Correct	194 ms	182392 KB	Output is correct
10	Correct	227 ms	182608 KB	Output is correct
11	Correct	200 ms	182332 KB	Output is correct
12	Correct	200 ms	182476 KB	Output is correct
13	Correct	179 ms	182400 KB	Output is correct
14	Correct	181 ms	182340 KB	Output is correct
15	Correct	248 ms	182380 KB	Output is correct
16	Correct	242 ms	182440 KB	Output is correct
17	Correct	179 ms	182544 KB	Output is correct
18	Correct	180 ms	182380 KB	Output is correct
19	Correct	242 ms	182372 KB	Output is correct
20	Correct	250 ms	182352 KB	Output is correct