Submission #841394

#	Time	Username	Problem	Language	Result	Execution time	Memory
841394		manizare	Growing Trees (BOI11_grow)	C++14	100 / 100	130 ms	7500 KiB

grow

#include <bits/stdc++.h> 

#define pb push_back 
#define F first 
#define S second 
#define all(a) a.begin(),a.end() 
#define pii pair<int,int>
#define int long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5 + 10 , maxk=1002 , sq = 333   , lg = 20 , K = 0,   inf = 1e18+10  , mod = 1e9 + 7 ;
int a[maxn] ,  seg[4*maxn] , lz[4*maxn]  , n , q ;

void shi(int p , int l , int r){
  int pl = p << 1 , pr = p << 1 | 1 , mid = (l+r) /2 ; 
  seg[pl] += lz[p] ; 
  lz[pl] += lz[p] ;
  seg[pr] += lz[p] ;
  lz[pr] += lz[p] ;
  lz[p] =0 ; 
}

void upd(int le , int ri , int val , int p= 1 , int l = 1, int r = n){
  int pl = p << 1 , pr = p << 1 | 1 , mid = (l+r) /2 ; 
  if(le > r || ri < l){
    return ; 
  } 
  if(l!=r)shi(p , l , r) ;
  if(le <= l && ri >= r){
    seg[p] += val ; 
    lz[p] += val;
    return ; 
  }
  upd(le , ri , val , pl ,l , mid) ;
  upd(le ,ri , val , pr , mid+1 ,r) ;
  seg[p]= seg[pr] ;
}
int find(int x ,int p = 1, int l = 1,  int r = n){
  int pl = p << 1 , pr = p << 1 | 1 , mid= (l+r)/2 ;
  if(l == r)return seg[p] ;
  shi(p , l , r) ;
  if(mid >= x){
    return find(x , pl , l, mid) ;
  }else{
    return find(x ,pr ,mid+1 , r) ;
  }
}
int lw(int x ,int p = 1 ,int l = 1 , int r = n){
  int pl = p << 1 , pr = p  << 1 | 1 , mid = (l+r) /2 ;
  if(l == r){
    if(seg[p] < x)return l+1 ;
    return l ;
  }
  shi(p, l , r) ;
  if(seg[pl] < x){
    return lw(x , pr , mid+1, r) ;
  }
  return lw(x , pl ,l , mid) ;
}


signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >> n >> q ;
  for(int i = 1  ; i <= n ; i++){
    cin >> a[i] ; 
  }
  sort(a+1 , a+1+n) ;
  for(int i= 1 ;i <= n ; i++){
    upd(i , i , a[i]) ;
  }
  while(q--){
    char a ;
    cin >> a;
    if(a == 'F'){
      int h , x ;
      cin >> x >> h ;
      int a = lw(h) ;
      if(a+x > n){
        upd(a , n , 1) ;
        continue ;
      }
      int rr =find(a+x-1); 
      int b = lw(rr) ;
      upd(a , b-1 , 1) ;
      int c = lw(rr+1) - 1; 
      upd(c- (a+x - b) + 1 , c , 1); 
    }else{
      int l , r ;
      cin >> l >> r; 
      cout << lw(r+1) - lw(l) << "\n" ;
    }
  }
}
/*  

*/

Compilation message (stderr)

grow.cpp: In function 'void shi(long long int, long long int, long long int)':
grow.cpp:15:39: warning: unused variable 'mid' [-Wunused-variable]
   15 |   int pl = p << 1 , pr = p << 1 | 1 , mid = (l+r) /2 ;
      |                                       ^~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10