oj.uz

답안 #838284

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
838284 2023-08-26T12:47:35 Z manizare 가로등 (APIO19_street_lamps) C++17
100 / 100
 2585 ms 160036 KB 
#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" ;
    }
  }
}
/*
 

*/

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

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 63828 KB Output is correct
2 Correct 33 ms 63700 KB Output is correct
3 Correct 32 ms 63700 KB Output is correct
4 Correct 31 ms 63680 KB Output is correct
5 Correct 31 ms 63652 KB Output is correct
6 Correct 31 ms 63664 KB Output is correct
7 Correct 31 ms 63700 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 71592 KB Output is correct
2 Correct 183 ms 71196 KB Output is correct
3 Correct 293 ms 71848 KB Output is correct
4 Correct 1347 ms 124708 KB Output is correct
5 Correct 1569 ms 131700 KB Output is correct
6 Correct 1091 ms 119932 KB Output is correct
7 Correct 2155 ms 142668 KB Output is correct
8 Correct 2093 ms 142916 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 63820 KB Output is correct
2 Correct 33 ms 63872 KB Output is correct
3 Correct 33 ms 63956 KB Output is correct
4 Correct 34 ms 64008 KB Output is correct
5 Correct 647 ms 91504 KB Output is correct
6 Correct 1110 ms 115316 KB Output is correct
7 Correct 1688 ms 135444 KB Output is correct
8 Correct 2462 ms 159300 KB Output is correct
9 Correct 149 ms 71152 KB Output is correct
10 Correct 163 ms 72700 KB Output is correct
11 Correct 168 ms 72644 KB Output is correct
12 Correct 2572 ms 158972 KB Output is correct
13 Correct 2379 ms 159240 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 63956 KB Output is correct
2 Correct 34 ms 63948 KB Output is correct
3 Correct 33 ms 63828 KB Output is correct
4 Correct 33 ms 63828 KB Output is correct
5 Correct 2497 ms 160036 KB Output is correct
6 Correct 1757 ms 141952 KB Output is correct
7 Correct 1152 ms 122108 KB Output is correct
8 Correct 603 ms 91064 KB Output is correct
9 Correct 243 ms 70492 KB Output is correct
10 Correct 156 ms 69944 KB Output is correct
11 Correct 232 ms 70524 KB Output is correct
12 Correct 169 ms 69948 KB Output is correct
13 Correct 239 ms 70464 KB Output is correct
14 Correct 153 ms 69956 KB Output is correct
15 Correct 2585 ms 159140 KB Output is correct
16 Correct 2434 ms 159260 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 63828 KB Output is correct
2 Correct 33 ms 63700 KB Output is correct
3 Correct 32 ms 63700 KB Output is correct
4 Correct 31 ms 63680 KB Output is correct
5 Correct 31 ms 63652 KB Output is correct
6 Correct 31 ms 63664 KB Output is correct
7 Correct 31 ms 63700 KB Output is correct
8 Correct 148 ms 71592 KB Output is correct
9 Correct 183 ms 71196 KB Output is correct
10 Correct 293 ms 71848 KB Output is correct
11 Correct 1347 ms 124708 KB Output is correct
12 Correct 1569 ms 131700 KB Output is correct
13 Correct 1091 ms 119932 KB Output is correct
14 Correct 2155 ms 142668 KB Output is correct
15 Correct 2093 ms 142916 KB Output is correct
16 Correct 32 ms 63820 KB Output is correct
17 Correct 33 ms 63872 KB Output is correct
18 Correct 33 ms 63956 KB Output is correct
19 Correct 34 ms 64008 KB Output is correct
20 Correct 647 ms 91504 KB Output is correct
21 Correct 1110 ms 115316 KB Output is correct
22 Correct 1688 ms 135444 KB Output is correct
23 Correct 2462 ms 159300 KB Output is correct
24 Correct 149 ms 71152 KB Output is correct
25 Correct 163 ms 72700 KB Output is correct
26 Correct 168 ms 72644 KB Output is correct
27 Correct 2572 ms 158972 KB Output is correct
28 Correct 2379 ms 159240 KB Output is correct
29 Correct 34 ms 63956 KB Output is correct
30 Correct 34 ms 63948 KB Output is correct
31 Correct 33 ms 63828 KB Output is correct
32 Correct 33 ms 63828 KB Output is correct
33 Correct 2497 ms 160036 KB Output is correct
34 Correct 1757 ms 141952 KB Output is correct
35 Correct 1152 ms 122108 KB Output is correct
36 Correct 603 ms 91064 KB Output is correct
37 Correct 243 ms 70492 KB Output is correct
38 Correct 156 ms 69944 KB Output is correct
39 Correct 232 ms 70524 KB Output is correct
40 Correct 169 ms 69948 KB Output is correct
41 Correct 239 ms 70464 KB Output is correct
42 Correct 153 ms 69956 KB Output is correct
43 Correct 2585 ms 159140 KB Output is correct
44 Correct 2434 ms 159260 KB Output is correct
45 Correct 92 ms 67960 KB Output is correct
46 Correct 158 ms 67960 KB Output is correct
47 Correct 695 ms 95596 KB Output is correct
48 Correct 1403 ms 129020 KB Output is correct
49 Correct 174 ms 72660 KB Output is correct
50 Correct 179 ms 72604 KB Output is correct
51 Correct 177 ms 72680 KB Output is correct
52 Correct 267 ms 75492 KB Output is correct
53 Correct 228 ms 75372 KB Output is correct
54 Correct 230 ms 75420 KB Output is correct