Submission #755284

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
755284	2023-06-09T17:01:07 Z	DonMichael	Monkey and Apple-trees (IZhO12_apple)	C++14	100 / 100	96 ms	3020 KB

apple

#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

static constexpr int N = 1e9;
static constexpr int LGN = 30;
static constexpr int M = 1e5;

struct Node {
  Node(void) = default;
  Node(int l, int r);

  int cl, cr;
  int l, r;
  bool red;
};

class DynamicSegmentTree {
public:
  DynamicSegmentTree(void);
  int query(int l, int r);
  void modify(int l, int r);
private:
  void add_left(int i);
  void add_right(int i);
  int _query(int i, int l, int r);
  void _modify(int i, int l, int r);

  Node t[M * LGN * 2];
  int cnt;
};

Node::Node(int l, int r): cl(0), cr(0), l(l), r(r), red(false) {
}

DynamicSegmentTree::DynamicSegmentTree(void): cnt(2) {
  t[1] = Node(0, N);
}

void DynamicSegmentTree::add_left(int i) {
  int c = t[i].cl = cnt++;
  t[c] = Node(t[i].l, (t[i].l + t[i].r) >> 1);
}

void DynamicSegmentTree::add_right(int i) {
  int c = t[i].cr = cnt++;
  t[c] = Node((t[i].l + t[i].r) >> 1, t[i].r);
}

int DynamicSegmentTree::_query(int i, int l, int r) {
  if (t[i].red)
    return r - l;
  int mid = (t[i].l + t[i].r) >> 1;
  if (r <= mid) {
    if (!t[i].cl)
      return 0;
    return _query(t[i].cl, l, r);
  }
  if (l >= mid) {
    if (!t[i].cr)
      return 0;
    return _query(t[i].cr, l, r);
  }
  int s = 0;
  if (t[i].cl)
    s += _query(t[i].cl, l, mid);
  if (t[i].cr)
    s += _query(t[i].cr, mid, r);
  return s;
}

inline int DynamicSegmentTree::query(int l, int r) {
  return _query(1, l, r);
}

void DynamicSegmentTree::_modify(int i, int l, int r) {
  if (t[i].red)
    return;
  if (t[i].l == l && t[i].r == r) {
    t[i].red = true;
  } else {
    int mid = (t[i].l + t[i].r) >> 1;
    if (r <= mid) {
      if (!t[i].cl)
        add_left(i);
      _modify(t[i].cl, l, r);
    } else if (l >= mid) {
      if (!t[i].cr)
        add_right(i);
      _modify(t[i].cr, l, r);
    } else {
      if (!t[i].cl)
        add_left(i);
      if (!t[i].cr)
        add_right(i);
      _modify(t[i].cl, l, mid);
      _modify(t[i].cr, mid, r);
    }
  }
}

inline void DynamicSegmentTree::modify(int l, int r) {
  _modify(1, l, r);
}

static DynamicSegmentTree dst;

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int m, c = 0;
  cin >> m;
  for (int i = 0; i < m; i++) {
    int d, x, y;
    cin >> d >> x >> y;
    if (d == 1)
      cout << (c = dst.query(c + x - 1, c + y)) << endl;
    else
      dst.modify(c + x - 1, c + y);
  }
  return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	1 ms	328 KB	Output is correct
3	Correct	1 ms	212 KB	Output is correct
4	Correct	8 ms	448 KB	Output is correct
5	Correct	10 ms	468 KB	Output is correct
6	Correct	10 ms	468 KB	Output is correct
7	Correct	9 ms	468 KB	Output is correct
8	Correct	48 ms	1372 KB	Output is correct
9	Correct	94 ms	2376 KB	Output is correct
10	Correct	96 ms	2424 KB	Output is correct
11	Correct	91 ms	2440 KB	Output is correct
12	Correct	89 ms	2380 KB	Output is correct
13	Correct	94 ms	2848 KB	Output is correct
14	Correct	96 ms	2768 KB	Output is correct
15	Correct	91 ms	3020 KB	Output is correct
16	Correct	92 ms	2936 KB	Output is correct
17	Correct	86 ms	2764 KB	Output is correct
18	Correct	88 ms	2868 KB	Output is correct
19	Correct	92 ms	2932 KB	Output is correct
20	Correct	92 ms	2888 KB	Output is correct