oj.uz

답안 #949537

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
949537 2024-03-19T10:26:12 Z nguyennh 원숭이와 사과 나무 (IZhO12_apple) C++14
0 / 100
 2000 ms 262144 KB 
#include<bits/stdc++.h>
#define el '\n'
using namespace std ;
 
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
 
const int MN = 1e5 + 5;

struct Node{
  int sum , lazy , l , r , child_l , child_r;
  Node () : sum(0) , lazy(0) , child_l(-1) , child_r(-1) {};
}; 

Node st[35 * MN];

int node = 2;

void fix(int id){
  if (!st[id].lazy) return;
  st[id].sum = st[id].r - st[id].l + 1;
  int mid = st[id].l + st[id].r >> 1;
  if (st[id].child_l == -1){
    st[id].child_l = node++;
    st[st[id].child_l].l = st[id].l;
    st[st[id].child_l].r = mid;
    st[st[id].child_l].lazy = 1;
  }
  if (st[id].child_r == -1){
    st[id].child_r = node++;
    st[st[id].child_r].l = mid + 1;
    st[st[id].child_r].r = st[id].r;
    st[st[id].child_r].lazy = 1;
  }
}

void update(int id , int l , int r){
  fix(id);
  if (st[id].l == l && st[id].r == r){
    st[id].lazy = 1;
    fix(id);
    return;
  }
  else {
    int mid = st[id].l + st[id].r >> 1;
    if (st[id].child_l == -1){
      st[id].child_l = node++;
      st[st[id].child_l].l = st[id].l;
      st[st[id].child_l].r = mid;
    }
    if (st[id].child_r == -1){
      st[id].child_r = node++;
      st[st[id].child_r].l = mid + 1;
      st[st[id].child_r].r = st[id].r;
    }
    if (l > mid) update(st[id].child_r , l , r);
    else if (r <= mid) update(st[id].child_l , l , r);
    else {
      update(st[id].child_l , l , mid);
      update(st[id].child_r , mid + 1 , r);
    }
    fix(st[id].child_l);
    fix(st[id].child_r);
    st[id].sum = st[st[id].child_l].sum + st[st[id].child_r].sum;
  }
}

int get(int id , int l , int r){
  fix(id);
  if (st[id].l == l && st[id].r == r){
    return st[id].sum;
  }
  else {
    int mid = st[id].l + st[id].r >> 1;
    if (st[id].child_l == -1){
      st[id].child_l = node++;
      st[st[id].child_l].l = st[id].l;
      st[st[id].child_l].r = mid;
    }
    if (st[id].child_r == -1){
      st[id].child_r = node++;
      st[st[id].child_r].l = mid + 1;
      st[st[id].child_r].r = st[id].r;
    }
    if (l > mid) return get(st[id].child_r , l , r);
    else if (r <= mid) return get(st[id].child_l , l , r);
    else {
      return get(st[id].child_l , l , mid) + get(st[id].child_r , mid + 1 , r);
    }
  }
}
 
int32_t main (){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int m;
  cin >> m;
  int last = 0;
  st[1].l = 1;
  st[1].r = (int)1e9;
  for ( int i = 1 ; i <= m ; i++ ){
    int type , l , r;
    cin >> type >> l >> r;
    l += last;
    r += last;
    if (type == 1){
      last = get(1 , l , r);
      cout << last << el;
    }
    else update(1 , l , r);
  }
}

Compilation message

apple.cpp: In function 'void fix(int)':
apple.cpp:21:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int mid = st[id].l + st[id].r >> 1;
      |             ~~~~~~~~~^~~~~~~~~~
apple.cpp: In function 'void update(int, int, int)':
apple.cpp:44:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = st[id].l + st[id].r >> 1;
      |               ~~~~~~~~~^~~~~~~~~~
apple.cpp: In function 'int get(int, int, int)':
apple.cpp:73:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   73 |     int mid = st[id].l + st[id].r >> 1;
      |               ~~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 82568 KB Output is correct
2 Correct 14 ms 82524 KB Output is correct
3 Execution timed out 2440 ms 262144 KB Time limit exceeded
4 Halted 0 ms 0 KB -