Submission #869291

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
869291	2023-11-04T01:24:42 Z	nima_aryan	Monkey and Apple-trees (IZhO12_apple)	C++17	0 / 100	2000 ms	157240 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;

class SparseLazySegmentTree {
 public:
  unordered_map<int, int> info;
  unordered_map<int, int> 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, int v) {
    if (v == 1) {
      info[p] = (r - l);
      tag[p] = 1;
    }
  }
  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] = 0;
  }

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

  void RangeApply(int p, int l, int r, int lx, int rx, int 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, int v) {
    RangeApply(1, 0, n, lx, rx, v);
  }

  int RangeQuery(int p, int l, int r, int lx, int rx) {
    if (l >= rx || r <= lx) {
      return 0;
    }
    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);
  }
  int RangeQuery(int lx, int rx) {
    return RangeQuery(1, 0, n, lx, rx);
  }
};

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

  constexpr int N = 1E9;
  SparseLazySegmentTree 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);
      cout << (C = res) << "\n";
    } else {
      seg.RangeApply(X, Y + 1, 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	54 ms	9172 KB	Output is correct
5	Correct	54 ms	10552 KB	Output is correct
6	Correct	54 ms	10308 KB	Output is correct
7	Correct	60 ms	10388 KB	Output is correct
8	Correct	881 ms	80800 KB	Output is correct
9	Correct	1884 ms	149148 KB	Output is correct
10	Execution timed out	2041 ms	157240 KB	Time limit exceeded
11	Halted	0 ms	0 KB	-