제출 #838284

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
838284		manizare	가로등 (APIO19_street_lamps)	C++17	100 / 100	2585 ms	160036 KiB

street_lamps

#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops")
#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" ;
    }
  }
}
/*
 

*/

컴파일 시 표준 에러 (stderr) 메시지

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20