Submission #949527

#	Time	Username	Problem	Language	Result	Execution time	Memory
949527		nguyennh	Monkey and Apple-trees (IZhO12_apple)	C++14	0 / 100	125 ms	262144 KiB

apple

#include<bits/stdc++.h>
#define el '\n'
#define int long long
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) , l(1) , r((int)1e9) , 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;
  }
}

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];
  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 (stderr)

apple.cpp: In function 'void fix(long long 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(long long int, long long int, long long 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 'long long int get(long long int, long long int, long long int)':
apple.cpp:74:24: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |     int mid = st[id].l + st[id].r >> 1;
      |               ~~~~~~~~~^~~~~~~~~~
apple.cpp: In function 'int32_t main()':
apple.cpp:99:7: warning: statement has no effect [-Wunused-value]
   99 |   st[1];
      |   ~~~~^

• Subtask 1: 0 / 100