Submission #869286

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869286	2023-11-04T01:16:42 Z	nima_aryan	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	2000 ms	86828 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:
  map<int, Info> info;
  map<int, Tag> tag;
  int n;

  SparseLazySegmentTree(int n) : n(n) { }

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

  void modify(int p, int l, int r, int x, const Info& v) {
    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(1, 0, n, x, v);
  }

  void RangeApply(int p, int l, int r, int lx, int rx, const Tag& v) {
    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(2 * p, l, m, lx, rx, v);
    RangeApply(2 * p + 1, m, r, lx, rx, v);
    pull(p);
  }
  void RangeApply(int lx, int rx, const Tag& v) {
    RangeApply(1, 0, n, lx, rx, v);
  }

  Info RangeQuery(int p, int l, int r, int lx, int rx) {
    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(2 * p, l, m, lx, rx) +
           RangeQuery(2 * p + 1, m, r, lx, rx);
  }
  Info RangeQuery(int lx, int rx) {
    return RangeQuery(1, 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};
}

constexpr int N = 1E9;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  SparseLazySegmentTree<Info, Tag> seg(N + 1);
  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

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	164 ms	9404 KB	Output is correct
5	Correct	218 ms	11352 KB	Output is correct
6	Correct	213 ms	11104 KB	Output is correct
7	Correct	219 ms	11344 KB	Output is correct
8	Execution timed out	2074 ms	86828 KB	Time limit exceeded
9	Halted	0 ms	0 KB	-