oj.uz

Submission #841394

# Submission time Handle Problem Language Result Execution time Memory
841394 2023-09-01T15:25:13 Z manizare Growing Trees (BOI11_grow) C++14
100 / 100
 130 ms 7500 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 6476 KB Output is correct
2 Correct 99 ms 6836 KB Output is correct
3 Correct 46 ms 6720 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 37 ms 1584 KB Output is correct
6 Correct 47 ms 1868 KB Output is correct
7 Correct 4 ms 724 KB Output is correct
8 Correct 20 ms 1364 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 1868 KB Output is correct
2 Correct 42 ms 2020 KB Output is correct
3 Correct 2 ms 652 KB Output is correct
4 Correct 23 ms 1492 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 2124 KB Output is correct
2 Correct 40 ms 1868 KB Output is correct
3 Correct 8 ms 724 KB Output is correct
4 Correct 41 ms 2000 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 4036 KB Output is correct
2 Correct 94 ms 6364 KB Output is correct
3 Correct 15 ms 2004 KB Output is correct
4 Correct 35 ms 6348 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 6196 KB Output is correct
2 Correct 85 ms 6468 KB Output is correct
3 Correct 40 ms 6632 KB Output is correct
4 Correct 13 ms 1876 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 6184 KB Output is correct
2 Correct 67 ms 6484 KB Output is correct
3 Correct 43 ms 6708 KB Output is correct
4 Correct 13 ms 1880 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 6800 KB Output is correct
2 Correct 91 ms 6348 KB Output is correct
3 Correct 37 ms 5836 KB Output is correct
4 Correct 62 ms 6220 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 6612 KB Output is correct
2 Correct 95 ms 6896 KB Output is correct
3 Correct 130 ms 6988 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 7500 KB Output is correct