답안 #959681

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
959681 2024-04-08T18:31:21 Z vjudge1 원숭이와 사과 나무 (IZhO12_apple) C++
0 / 100
449 ms 262144 KB
#include<bits/stdc++.h>
using namespace std;
const long long int MAX_N = 1000000000;
const long long int NIL = -1;

class SparseSegmentTree{
  public:
  SparseSegmentTree(long long int number_of_datum){
    n = 1;
    while(n < number_of_datum) n *= 2;
    root = new Node(0, n);
  }
  void range_update(long long int s, long long int t){
    inner_add(s, t + 1, root);
  }
  long long int range_query(long long int s, long long int t){
    return inner_getsum(s, t + 1, root);
  }
  private:
  struct Node{
    long long int left_bound, right_bound;
    long long int dat, laz = NIL;
    Node *left_child, *right_child;
    Node(long long int lb, long long int rb){
      left_bound = lb;
      right_bound = rb;
    }
  };
  void inner_split(Node *node){
    if(node->left_child) return;
    long long int l = node->left_bound;
    long long int r = node->right_bound;
    if(l + 1 == r) return;
    long long 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(long long int a, long long int b, Node *node){
    long long int l = node->left_bound;
    long long 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;
  }
  long long int inner_getsum(long long int a, long long int b, Node *node){
    if(!node) return 0;
    long long int l = node->left_bound;
    long long 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);
  }
  long long 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);
  long long int C = 0;
  while(q--){
    int op;
    cin >> op;
    if(op == 2){
      long long int s, t;
      cin >> s >> t;
      s--;
      t--;
      st.range_update(s + C, t + C);
    }else{
      long long int s, t;
      cin >> s >> t;
      s--;
      t--;
      long long int res = st.range_query(s + C, t + C);
      cout << res << endl;
      C = res;
    }
  }
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 504 KB Output is correct
4 Correct 14 ms 6172 KB Output is correct
5 Correct 18 ms 7512 KB Output is correct
6 Correct 19 ms 7256 KB Output is correct
7 Correct 18 ms 7516 KB Output is correct
8 Correct 127 ms 55636 KB Output is correct
9 Correct 265 ms 99664 KB Output is correct
10 Correct 286 ms 106592 KB Output is correct
11 Correct 278 ms 115028 KB Output is correct
12 Correct 292 ms 118452 KB Output is correct
13 Correct 303 ms 140368 KB Output is correct
14 Correct 260 ms 141620 KB Output is correct
15 Correct 449 ms 259152 KB Output is correct
16 Correct 412 ms 262024 KB Output is correct
17 Correct 269 ms 146524 KB Output is correct
18 Correct 262 ms 146708 KB Output is correct
19 Runtime error 408 ms 262144 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -