Submission #950310

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
950310	2024-03-20T07:55:09 Z	nguyennh	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	95 ms	262144 KB

apple

#include<bits/stdc++.h>
#define el '\n'
using namespace std ;
 
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
 
const int MN = 123456;
 
struct Node{
  int sum , lazy , l , r , child_l , child_r;
  Node () : sum(0) , lazy(0) , child_l(-1) , child_r(-1) {};
}; 
 
Node st[64 * 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;
  }
  st[id].lazy = 0;
}
 
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:45:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int mid = st[id].l + st[id].r >> 1;
      |               ~~~~~~~~~^~~~~~~~~~
apple.cpp: In function 'int get(int, int, int)':
apple.cpp:74:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |     int mid = st[id].l + st[id].r >> 1;
      |               ~~~~~~~~~^~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	74 ms	185908 KB	Output is correct
2	Correct	41 ms	185936 KB	Output is correct
3	Runtime error	95 ms	262144 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-