Submission #949539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
949539	2024-03-19T10:29:02 Z	nguyennh	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	1102 ms	262144 KB

apple

#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#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;
  }
  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:22:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |   int mid = st[id].l + st[id].r >> 1;
      |             ~~~~~~~~~^~~~~~~~~~
apple.cpp: In function 'void update(int, int, int)':
apple.cpp:46:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     int mid = st[id].l + st[id].r >> 1;
      |               ~~~~~~~~~^~~~~~~~~~
apple.cpp: In function 'int get(int, int, int)':
apple.cpp:75:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   75 |     int mid = st[id].l + st[id].r >> 1;
      |               ~~~~~~~~~^~~~~~~~~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	82516 KB	Output is correct
2	Correct	17 ms	82524 KB	Output is correct
3	Runtime error	1102 ms	262144 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-