제출 #959683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
959683		vjudge1	원숭이와 사과 나무 (IZhO12_apple)	C++98	100 / 100	381 ms	202832 KiB

apple

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 1000000000;
const int NIL = -1;

class SparseSegmentTree{
  public:
  SparseSegmentTree(int number_of_datum){
    n = 1;
    while(n < number_of_datum) n *= 2;
    root = new Node(0, n);
  }
  void range_update(int s, int t){
    inner_add(s, t + 1, root);
  }
  int range_query(int s, int t){
    return inner_getsum(s, t + 1, root);
  }
  private:
  struct Node{
    int left_bound, right_bound;
    int dat, laz = NIL;
    Node *left_child, *right_child;
    Node(int lb, int rb){
      left_bound = lb;
      right_bound = rb;
    }
  };
  void inner_split(Node *node){
    if(node->left_child) return;
    int l = node->left_bound;
    int r = node->right_bound;
    if(l + 1 == r) return;
    int mid = (l + r) / 2;
    node->left_child = new Node(l, mid);
    node->right_child = new Node(mid, r);
  }
  void inner_prop(Node *node){
    inner_split(node);
    if(!node->left_child) return;
    if(node->laz == NIL) return;
    node->left_child->dat = node->laz / 2;
    node->right_child->dat = node->laz / 2;
    node->left_child->laz = node->laz / 2;
    node->right_child->laz = node->laz / 2;
    node->laz = NIL;
  }
  void inner_add(int a, int b, Node *node){
    int l = node->left_bound;
    int r = node->right_bound;
    if(b <= l || r <= a) return;
    if(a <= l && r <= b){
      node->dat = r - l;
      node->laz = r - l;
      return;
    }
    inner_prop(node);
    if(!node->left_child) return;
    inner_add(a, b, node->left_child);
    inner_add(a, b, node->right_child);
    node->dat = node->left_child->dat + node->right_child->dat;
  }
  int inner_getsum(int a, int b, Node *node){
    if(!node) return 0;
    int l = node->left_bound;
    int r = node->right_bound;
    if(b <= l || r <= a) return 0;
    if(a <= l && r <= b) return node->dat;
    inner_prop(node);
    return inner_getsum(a, b, node->left_child) + inner_getsum(a, b, node->right_child);
  }
  int n;
  Node *root;
};

int q;

int main(){
  cin.tie(0);
  cout.tie(0);
  ios::sync_with_stdio(false);
  cin >> q;
  SparseSegmentTree st(MAX_N);
  int C = 0;
  while(q--){
    int op;
    cin >> op;
    if(op == 2){
      int s, t;
      cin >> s >> t;
      s--;
      t--;
      st.range_update(s + C, t + C);
    }else{
      int s, t;
      cin >> s >> t;
      s--;
      t--;
      int res = st.range_query(s + C, t + C);
      cout << res << endl;
      C = res;
    }
  }
  return 0;
}

• Subtask 1: 100 / 100