oj.uz

Submission #838278

# Submission time Handle Problem Language Result Execution time Memory
838278 2023-08-26T12:41:06 Z manizare Street Lamps (APIO19_street_lamps) C++17
100 / 100
 2564 ms 165248 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>
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e5 + 10 ,  inf = 1e9+10  ;
int ls[maxn]  , fen[maxn]  , pre[maxn] , n , q  ;
vector <int> vec[maxn * 4] , fenw[4*maxn]; 
vector <pii> pors[maxn] ; 
void upd(int x ,int val){
  x++; 
  while(x <= (n+2)){
    fen[x] += val ;
    x += x&-x ;
  }
}
int que(int x){
  x++ ;
  int ans= 0 ;
  while(x){
    ans += fen[x] ; 
    x -= x&-x; 
  }
  return ans ;
}
void upd2(int ty , int x ,int val){
  x++; 
  while(x < fenw[ty].size()){
    fenw[ty][x] += val ;
    x += x&-x ;
  }
}
int que2(int ty , int x){
  x++ ;
  int ans= 0 ;
  while(x){
    ans += fenw[ty][x] ; 
    x -= x&-x; 
  }
  return ans ;
}
void bui(int p = 1 , int l  =0  , int r = n){
  int pl = p << 1 , pr = p << 1 | 1 , mid = (l+r) >> 1 ;
  if(l == r){
    for(int i = 0 ; i < pors[l].size() ; i++){
      vec[p].pb(pors[l][i].S) ;   
    }
    sort(all(vec[p])) ;
    vec[p].resize(unique(all(vec[p]))-vec[p].begin()) ;
    reverse(all(vec[p]));
    for(int i = 0 ; i <= vec[p].size() + 2  ; i++){
      fenw[p].pb(0) ; 
    }
    return ; 
  }
  bui(pl , l , mid) ; 
  bui(pr, mid+1 ,r); 
  vec[p] = vec[pl] ;
  for(int i =0 ; i < vec[pr].size() ; i++){
    vec[p].pb(vec[pr][i]) ;
  }
  sort(all(vec[p])) ;
  vec[p].resize(unique(all(vec[p]))-vec[p].begin()) ;
  reverse(all(vec[p]));
  for(int i = 0 ; i <= vec[p].size()+2  ; i++){
    fenw[p].pb(0) ; 
  }
}
 
void az(int le , int ri , int val , int R , int p = 1 , int l = 0 , int r = n){
  int pl = p << 1 , pr = p << 1 | 1, mid = (l+r) >> 1; 
  if(p == 1){
 //   cout << le << " " <<ri << " "<< val << " "<< R << "<--\n" ;
  }
  if(le > r || l > ri)return ; 
  if(l >= le && ri >= r){
    int ll = -1  , rr = vec[p].size() ; 
    while(rr-ll > 1){
      int mid = (ll+rr) >> 1 ;
      if(vec[p][mid] <= R)rr = mid ;
      else ll = mid ;
    }
    upd2(p , rr , val) ;
    return ; 
  }
  az(le , ri , val , R , pl , l , mid) ; 
  az(le , ri , val , R , pr , mid+1, r) ; 
}
int javab (int x , int R ,  int p = 1 ,int l = 0 , int r = n){
  int pl = p << 1 , pr = p << 1 | 1 , mid = (l + r) >>  1; 
  if(x > r || l > x)return 0 ;
  int ll = -1  , rr = vec[p].size() ; 
  while(rr-ll > 1){
    int mid = (ll+rr) >> 1 ;
    if(vec[p][mid] <= R)rr = mid ;
    else ll = mid ;
  }  
  if(x==l && x == r)return que2(p , rr) ;
  return javab(x , R , pl , l , mid) + javab(x , R , pr , mid+1 ,r) + que2(p , rr) ; 
}
signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  cin >>n >> q;
  string s;
  cin >> s; 
  s=  "0" + s;
  pre[0] = 1;  
  for(int i =1 ; i <= n ; i++){
    pre[i] = pre[i-1] + (s[i] == '0') ; 
  }
  for(int i = 0 ;i  <= n; i ++){
    if(s[i] == '0'){
      upd(i , 1) ;
    }
  }
  vector <pair <int ,pii> > qu ;
  for(int i =1 ; i <= q; i ++){
    string a;
    cin >> a;  
    if(a[0] == 'q'){
      int l , r ;
      cin >> l >> r ; 
      r--;l--;
      pors[l].pb({i , r}) ; 
      qu.pb({0 , {l , r}}) ; 
    }else{
      int x;
      cin >> x; 
      qu.pb({1 , {x , x}}) ;
    }
  }
  bui();
  for(int i = 1 ; i <= q ; i++){
    int ty = qu[i-1].F , l = qu[i-1].S.F , r = qu[i-1].S.S ; 
    if(ty == 1){
      int a = que(l-1) , b=  que(l) ;
      if(a==b){
        int le = -1 , ri = l ; 
        while(ri-le > 1){
          int mid = (le + ri) / 2;   
          if(que(mid) == a){
            ri = mid ;
          }else{
            le = mid ; 
          }
        }
        int rr = ri ; 
        le = l , ri = n+1 ;
        while(ri-le > 1){
          int mid = (le + ri) / 2;   
          if(que(mid) == a){
            le = mid ;
          }else{
            ri = mid ; 
          }
        }
        az(rr , le , i - ls[le] , le) ;
        ls[le] = ls[l-1] = i ; 
      }
      if(s[l] == '0'){
        s[l] = '1' ;
        upd(l , -1) ; 
      }else{
        s[l] = '0' ;
        upd(l , 1) ;
      }
      if(a==b)continue ;
      int aa = que(l-1) , bb = que(l) ; 
      if(a != b && aa == bb){
        int le= -1 , ri = l-1 ;
        while(ri-le > 1){
          int mid = (le + ri)/2 ;
          if(que(mid) == aa)ri = mid ;
          else le = mid ;
        }
        az(ri , l-1 , i-ls[l-1] , l-1);
        le= l , ri = n+1 ;
        while(ri - le > 1){
          int mid =(le + ri)/2 ;
          if(que(mid) == bb){
            le = mid ;
          }else{
            ri = mid ; 
          }
        }
        az(l , le, i-ls[le] , le);
        ls[le] = i ;
      }
    }
    else {
      int le = l , ri = n+1;
      int z =que(l) ; 
      while(ri - le > 1){
        int mid = (le + ri) / 2;
        if(que(mid )== z)le = mid ;
        else ri = mid ;
      }
      int ans = javab(l, r) ;
      if(r <= le){
        ans += i-ls[le] ;
      }
      cout << ans << "\n" ;
    }
  }
}
/*
 

*/

Compilation message

street_lamps.cpp: In function 'void upd2(int, int, int)':
street_lamps.cpp:32:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   while(x < fenw[ty].size()){
      |         ~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'void bui(int, int, int)':
street_lamps.cpp:49:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i = 0 ; i < pors[l].size() ; i++){
      |                     ~~^~~~~~~~~~~~~~~~
street_lamps.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i = 0 ; i <= vec[p].size() + 2  ; i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |   for(int i =0 ; i < vec[pr].size() ; i++){
      |                  ~~^~~~~~~~~~~~~~~~
street_lamps.cpp:69:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for(int i = 0 ; i <= vec[p].size()+2  ; i++){
      |                   ~~^~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 63820 KB Output is correct
2 Correct 30 ms 63700 KB Output is correct
3 Correct 31 ms 63692 KB Output is correct
4 Correct 30 ms 63700 KB Output is correct
5 Correct 29 ms 63700 KB Output is correct
6 Correct 30 ms 63700 KB Output is correct
7 Correct 29 ms 63708 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 71700 KB Output is correct
2 Correct 180 ms 74548 KB Output is correct
3 Correct 290 ms 75924 KB Output is correct
4 Correct 1280 ms 129844 KB Output is correct
5 Correct 1585 ms 136976 KB Output is correct
6 Correct 1060 ms 124756 KB Output is correct
7 Correct 2135 ms 148564 KB Output is correct
8 Correct 2056 ms 148900 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 63820 KB Output is correct
2 Correct 32 ms 63828 KB Output is correct
3 Correct 32 ms 64012 KB Output is correct
4 Correct 33 ms 63956 KB Output is correct
5 Correct 630 ms 94836 KB Output is correct
6 Correct 1146 ms 120112 KB Output is correct
7 Correct 1651 ms 140776 KB Output is correct
8 Correct 2431 ms 165248 KB Output is correct
9 Correct 144 ms 73892 KB Output is correct
10 Correct 154 ms 75720 KB Output is correct
11 Correct 160 ms 75772 KB Output is correct
12 Correct 2491 ms 164960 KB Output is correct
13 Correct 2423 ms 165224 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 63956 KB Output is correct
2 Correct 33 ms 64076 KB Output is correct
3 Correct 32 ms 63828 KB Output is correct
4 Correct 32 ms 63828 KB Output is correct
5 Correct 2461 ms 164988 KB Output is correct
6 Correct 1756 ms 147408 KB Output is correct
7 Correct 1096 ms 126964 KB Output is correct
8 Correct 587 ms 95368 KB Output is correct
9 Correct 225 ms 73804 KB Output is correct
10 Correct 150 ms 72812 KB Output is correct
11 Correct 233 ms 73780 KB Output is correct
12 Correct 153 ms 72764 KB Output is correct
13 Correct 229 ms 73776 KB Output is correct
14 Correct 151 ms 72828 KB Output is correct
15 Correct 2564 ms 164992 KB Output is correct
16 Correct 2356 ms 165100 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 63820 KB Output is correct
2 Correct 30 ms 63700 KB Output is correct
3 Correct 31 ms 63692 KB Output is correct
4 Correct 30 ms 63700 KB Output is correct
5 Correct 29 ms 63700 KB Output is correct
6 Correct 30 ms 63700 KB Output is correct
7 Correct 29 ms 63708 KB Output is correct
8 Correct 146 ms 71700 KB Output is correct
9 Correct 180 ms 74548 KB Output is correct
10 Correct 290 ms 75924 KB Output is correct
11 Correct 1280 ms 129844 KB Output is correct
12 Correct 1585 ms 136976 KB Output is correct
13 Correct 1060 ms 124756 KB Output is correct
14 Correct 2135 ms 148564 KB Output is correct
15 Correct 2056 ms 148900 KB Output is correct
16 Correct 32 ms 63820 KB Output is correct
17 Correct 32 ms 63828 KB Output is correct
18 Correct 32 ms 64012 KB Output is correct
19 Correct 33 ms 63956 KB Output is correct
20 Correct 630 ms 94836 KB Output is correct
21 Correct 1146 ms 120112 KB Output is correct
22 Correct 1651 ms 140776 KB Output is correct
23 Correct 2431 ms 165248 KB Output is correct
24 Correct 144 ms 73892 KB Output is correct
25 Correct 154 ms 75720 KB Output is correct
26 Correct 160 ms 75772 KB Output is correct
27 Correct 2491 ms 164960 KB Output is correct
28 Correct 2423 ms 165224 KB Output is correct
29 Correct 33 ms 63956 KB Output is correct
30 Correct 33 ms 64076 KB Output is correct
31 Correct 32 ms 63828 KB Output is correct
32 Correct 32 ms 63828 KB Output is correct
33 Correct 2461 ms 164988 KB Output is correct
34 Correct 1756 ms 147408 KB Output is correct
35 Correct 1096 ms 126964 KB Output is correct
36 Correct 587 ms 95368 KB Output is correct
37 Correct 225 ms 73804 KB Output is correct
38 Correct 150 ms 72812 KB Output is correct
39 Correct 233 ms 73780 KB Output is correct
40 Correct 153 ms 72764 KB Output is correct
41 Correct 229 ms 73776 KB Output is correct
42 Correct 151 ms 72828 KB Output is correct
43 Correct 2564 ms 164992 KB Output is correct
44 Correct 2356 ms 165100 KB Output is correct
45 Correct 88 ms 69888 KB Output is correct
46 Correct 130 ms 70036 KB Output is correct
47 Correct 660 ms 98816 KB Output is correct
48 Correct 1405 ms 134048 KB Output is correct
49 Correct 168 ms 75876 KB Output is correct
50 Correct 177 ms 75812 KB Output is correct
51 Correct 178 ms 76544 KB Output is correct
52 Correct 229 ms 79412 KB Output is correct
53 Correct 223 ms 79340 KB Output is correct
54 Correct 230 ms 79284 KB Output is correct