Submission #869290

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

struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    // http://xorshift.di.unimi.it/splitmix64.c
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }

  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};

class SparseLazySegmentTree {
 public:
  unordered_map<int, int, custom_hash> info;
  unordered_map<int, int, custom_hash> 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	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	80 ms	9252 KB	Output is correct
5	Correct	90 ms	10552 KB	Output is correct
6	Correct	91 ms	10132 KB	Output is correct
7	Correct	101 ms	10316 KB	Output is correct
8	Correct	1409 ms	80788 KB	Output is correct
9	Execution timed out	2056 ms	108072 KB	Time limit exceeded
10	Halted	0 ms	0 KB	-