Submission #869300

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869300	2023-11-04T01:51:36 Z	nima_aryan	Monkey and Apple-trees (IZhO12_apple)	C++17	100 / 100	263 ms	159664 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;

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

  int n;

  SparseLazySegmentTree(int n, int alpha) : n(n) {
    info.resize(alpha), tag.resize(alpha);
    nodes.resize(alpha);
  }

  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;
  SparseLazySegmentTree<Info, Tag> seg(N + 1, A);

  int M;
  cin >> 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	101 ms	157008 KB	Output is correct
2	Correct	24 ms	157016 KB	Output is correct
3	Correct	25 ms	157104 KB	Output is correct
4	Correct	33 ms	157012 KB	Output is correct
5	Correct	38 ms	157016 KB	Output is correct
6	Correct	36 ms	157020 KB	Output is correct
7	Correct	41 ms	156988 KB	Output is correct
8	Correct	99 ms	157076 KB	Output is correct
9	Correct	228 ms	157268 KB	Output is correct
10	Correct	201 ms	157264 KB	Output is correct
11	Correct	195 ms	158984 KB	Output is correct
12	Correct	247 ms	159060 KB	Output is correct
13	Correct	196 ms	159572 KB	Output is correct
14	Correct	179 ms	159500 KB	Output is correct
15	Correct	263 ms	159652 KB	Output is correct
16	Correct	243 ms	159600 KB	Output is correct
17	Correct	181 ms	159476 KB	Output is correct
18	Correct	181 ms	159508 KB	Output is correct
19	Correct	234 ms	159572 KB	Output is correct
20	Correct	234 ms	159664 KB	Output is correct