#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimization ("O2")
#define lp(i,a,b) for(int i = a; i < b; i++)
#define pb push_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define debug //printf
#define tiii tuple<int,int,int>
#define mkt make_tuple
#define pii pair<int,int>
#define mk make_pair
#define ll long long
#define ff first
#define ss second
const int MAXN = 3e5+10 ;
using namespace std ;
struct SegNode
{
vector<int> e , d , soma , lz ;
int create()
{
e.pb(0);
d.pb(0);
lz.pb(0) ;
soma.pb(0);
return sz(e) - 1 ;
}
int m(int l, int r) { return (l+r)>>1 ; }
void refresh(int pos, int l , int r)
{
soma[pos] += lz[pos] * (r-l+1) ;
if(l==r) return (void)(lz[pos]=0) ;
int aux ;
if( !e[pos]) aux = create() , e[pos] = aux ;
lz[ e[pos] ] += lz[pos] ;
if(!d[pos]) aux = create() , d[pos] = aux ;
lz[ d[pos] ] += lz[pos] ;
lz[pos] = 0 ;
}
void upd(int pos, int l,int r, int beg, int en , int val)
{
debug("Updatando %d %d com %d\n" , beg, en ,val ) ;
if(!pos) return ;
if(lz[pos] != 0) refresh(pos,l,r) ;
if( l > en || r < beg ) return ;
if(l >= beg && r <= en)
{
lz[pos] += val ;
refresh(pos,l,r) ;
return ;
}
int aux ;
if(!e[pos]) aux = create() , e[pos] = aux ;
upd(e[pos] , l , m(l,r) , beg, en , val ) ;
if(!d[pos]) aux = create() , d[pos] = aux ;
upd(d[pos] , m(l,r)+1, r, beg, en , val ) ;
soma[pos] = soma[ e[pos] ] + soma[ d[pos] ] ;
}
int qry(int pos, int l , int r, int k)
{
if(!pos) return 0 ;
if(lz[pos] != 0) refresh(pos,l,r) ;
debug("Estou em %d %d, procurando %d, e minha soma eh %d e minha lz eh %d\n" , l , r , k , soma[pos], lz[pos]) ;
if(l==r) return soma[pos] ;
int aux ;
if( k <= m(l,r) )
{
if( e[pos] == 0 ) aux = create() , e[pos] = aux ;
return qry( e[pos] , l ,m(l,r) , k ) ;
}
else
{
if( d[pos] == 0 ) aux = create() , d[pos] = aux ;
return qry( d[pos] , m(l,r)+1, r , k) ;
}
}
};
struct Seg
{
int n ;
SegNode tree[MAXN*2] ;
Seg() { for(int i = 0 ; i < MAXN*2 ; i++ ) tree[i].create() , tree[i].create() ; }
void upd( int beg, int en, int l1, int l2, int toSum )
{
for(beg += n , en += n ; beg < en ; beg >>= 1 , en >>= 1 )
{
if(beg&1)
{
debug("Entrei em %d\n" , beg ) ;
tree[beg].upd(1,1,n,l1,l2,toSum) ;
beg++ ;
}
if(en&1)
{
en--;
debug("Entrei em %d\n" , en ) ;
tree[en].upd(1,1,n, l1, l2, toSum ) ;
}
}
}
int qry(int x, int y)
{
int tot = 0 ;
for(x += n ; x >= 1 ; x >>= 1 )
{
int val = tree[x].qry( 1 , 1 , n , y ) ;
debug("Query em %d e %d, consegui %d\n" , x , y ,val ) ;
tot += val ;
}
return tot ;
}
} seg ;
int N , Q ;
set<pii> intervalos ;
char str[MAXN] , q[MAXN] ;
int main()
{
scanf("%d%d", &N , &Q ) ;
scanf("%s", str ) ;
str[N] = 0 ;
N++;
seg.n = N+1 ;
for(int i = 0 ; i < N ; i++ )
{
int j = i ;
while( j < N && str[j] == '1' ) j++ ;
debug("Achei o intervalo %d %d\n" , i+1 , j+1 ) ;
//O intervalo eh [i,j-1]
intervalos.insert( mk(i+1,j+1) ) ;
seg.upd( i,j+1 , i+1, j+1 , -1 ) ;
i = j ;
}
for(int i = 1 ; i <= Q ; i++ )
{
scanf("%s", q ) ;
if(q[0] == 'q')
{
int a , b , segQuery ;
scanf("%d%d", &a, &b );
segQuery = seg.qry(a-1, b) ;
auto it = intervalos.upper_bound( mk(a,N+5) ) ;
it-- ;
if( it->ss >= b ) segQuery += i+1 ;
printf("%d\n" , segQuery ) ;
}
else
{
int lamp ;
scanf("%d", &lamp ) ;
auto meContem = intervalos.upper_bound(mk(lamp,N+5)) ;
meContem--;
debug("Estou no intervalo %d %d\n" , meContem->ff, meContem->ss ) ;
if( str[lamp-1] == '0' )
{
pii toInsert=*meContem ;
auto prox = meContem ; prox++ ;
toInsert.ss = prox->ss ;
intervalos.erase(prox) ;
meContem = intervalos.upper_bound(mk(lamp,N+5)) ; meContem-- ;
intervalos.erase(meContem) ;
intervalos.insert( toInsert ) ;
seg.upd(toInsert.ff-1,lamp, lamp+1, toInsert.ss, -i-1 ) ;
str[lamp-1] = '1' ;
}
else
{
pii toInsert1 = mk(meContem->ff,lamp) ;
pii toInsert2 = mk(lamp+1, meContem->ss ) ;
seg.upd(toInsert1.ff-1, toInsert1.ss, toInsert2.ff, toInsert2.ss , i) ;
intervalos.erase( meContem ) ;
intervalos.insert(toInsert1) ;
intervalos.insert(toInsert2) ;
str[lamp-1] = '0' ;
}
}
}
}
/*
5 9
11011
query 1 2
query 1 2
query 1 6
query 3 4
toggle 3
query 3 4
query 1 6
toggle 3
query 1 6
*/
Compilation message
street_lamps.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
5 | #pragma GCC optimization ("unroll-loops")
|
street_lamps.cpp:6: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
6 | #pragma GCC optimization ("O2")
|
street_lamps.cpp: In member function 'void SegNode::upd(int, int, int, int, int, int)':
street_lamps.cpp:63:15: warning: left operand of comma operator has no effect [-Wunused-value]
63 | debug("Updatando %d %d com %d\n" , beg, en ,val ) ;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:63:49: warning: right operand of comma operator has no effect [-Wunused-value]
63 | debug("Updatando %d %d com %d\n" , beg, en ,val ) ;
| ^~
street_lamps.cpp:63:53: warning: right operand of comma operator has no effect [-Wunused-value]
63 | debug("Updatando %d %d com %d\n" , beg, en ,val ) ;
| ^~~
street_lamps.cpp: In member function 'int SegNode::qry(int, int, int, int)':
street_lamps.cpp:95:15: warning: left operand of comma operator has no effect [-Wunused-value]
95 | debug("Estou em %d %d, procurando %d, e minha soma eh %d e minha lz eh %d\n" , l , r , k , soma[pos], lz[pos]) ;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:95:92: warning: right operand of comma operator has no effect [-Wunused-value]
95 | debug("Estou em %d %d, procurando %d, e minha soma eh %d e minha lz eh %d\n" , l , r , k , soma[pos], lz[pos]) ;
| ^
street_lamps.cpp:95:97: warning: right operand of comma operator has no effect [-Wunused-value]
95 | debug("Estou em %d %d, procurando %d, e minha soma eh %d e minha lz eh %d\n" , l , r , k , soma[pos], lz[pos]) ;
| ^
street_lamps.cpp:95:109: warning: right operand of comma operator has no effect [-Wunused-value]
95 | debug("Estou em %d %d, procurando %d, e minha soma eh %d e minha lz eh %d\n" , l , r , k , soma[pos], lz[pos]) ;
| ^
street_lamps.cpp: In member function 'void Seg::upd(int, int, int, int, int)':
street_lamps.cpp:131:23: warning: left operand of comma operator has no effect [-Wunused-value]
131 | debug("Entrei em %d\n" , beg ) ;
| ^~~~~~~~~~~~~~~~
street_lamps.cpp:138:23: warning: left operand of comma operator has no effect [-Wunused-value]
138 | debug("Entrei em %d\n" , en ) ;
| ^~~~~~~~~~~~~~~~
street_lamps.cpp: In member function 'int Seg::qry(int, int)':
street_lamps.cpp:153:19: warning: left operand of comma operator has no effect [-Wunused-value]
153 | debug("Query em %d e %d, consegui %d\n" , x , y ,val ) ;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:153:59: warning: right operand of comma operator has no effect [-Wunused-value]
153 | debug("Query em %d e %d, consegui %d\n" , x , y ,val ) ;
| ^
street_lamps.cpp:153:63: warning: right operand of comma operator has no effect [-Wunused-value]
153 | debug("Query em %d e %d, consegui %d\n" , x , y ,val ) ;
| ^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:183:15: warning: left operand of comma operator has no effect [-Wunused-value]
183 | debug("Achei o intervalo %d %d\n" , i+1 , j+1 ) ;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:183:46: warning: right operand of comma operator has no effect [-Wunused-value]
183 | debug("Achei o intervalo %d %d\n" , i+1 , j+1 ) ;
| ~^~
street_lamps.cpp:223:19: warning: left operand of comma operator has no effect [-Wunused-value]
223 | debug("Estou no intervalo %d %d\n" , meContem->ff, meContem->ss ) ;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:169:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
169 | scanf("%d%d", &N , &Q ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:170:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
170 | scanf("%s", str ) ;
| ~~~~~^~~~~~~~~~~~
street_lamps.cpp:196:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
196 | scanf("%s", q ) ;
| ~~~~~^~~~~~~~~~
street_lamps.cpp:202:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
202 | scanf("%d%d", &a, &b );
| ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:218:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
218 | scanf("%d", &lamp ) ;
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
131832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
589 ms |
133112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
302 ms |
132832 KB |
Output is correct |
| 2 |
Correct |
303 ms |
133112 KB |
Output is correct |
| 3 |
Correct |
297 ms |
133496 KB |
Output is correct |
| 4 |
Correct |
299 ms |
133112 KB |
Output is correct |
| 5 |
Runtime error |
2512 ms |
524292 KB |
Execution killed with signal 9 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
304 ms |
133500 KB |
Output is correct |
| 2 |
Incorrect |
331 ms |
133368 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
131832 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
