제출 #755284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
755284		DonMichael	원숭이와 사과 나무 (IZhO12_apple)	C++14	100 / 100	96 ms	3020 KiB

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 / 100