#include <bits/stdc++.h>
static struct FASTIO {
char READ_CHARACTER; bool REMAINING_CHARACTER = false;
inline void ignore(); inline void flush();
template <typename T> inline bool READ_INT(T &x); template <typename T> inline bool READ_STRING(T &x);
/* Fast I/O Code Optimizer */
template<size_t N> inline bool READ_CHAR_ARRAY(char (&x)[N]); template<size_t N> inline bool READ_VAR(char (&x)[N]);
/* A tool to optimize execution time of C++ codes by replacing methods of reading and writing variables */
template <typename T> inline bool READ_CHAR(T &x); inline bool READ_CHAR_ARRAY(char*& x); inline bool READ_GETLINE(std::string &x);
/* Use it on fastio.pythonanywhere.com */
template <typename T> inline bool READ_FLOAT(T &x); template <typename T> inline bool READ_DOUBLE(T &x);
/* Github Project: github.com/bfs07/Fast-IO-Code-Optimizer */
template<std::size_t N> inline bool READ_BITSET(std::bitset<N> &bit); template<std::size_t N> inline bool READ_VAR(std::bitset<N> &bit);
inline bool READ_VAR(bool &x); inline bool READ_VAR(short int &x); inline bool READ_VAR(int &x);
inline bool READ_VAR(long int &x); inline bool READ_VAR(long long int &x); inline bool READ_VAR(unsigned short int &x);
inline bool READ_VAR(unsigned int &x); inline bool READ_VAR(unsigned long &x); inline bool READ_VAR(unsigned long long &x);
inline bool READ_VAR(std::string &x); inline bool READ_VAR(char &x); inline bool READ_VAR(char*& x); inline bool READ_VAR(float &x);
inline bool READ_VAR(double &x); inline bool READ_VAR(long double &x); template <typename T> inline void WRITE_INT(T x);
inline void WRITE_STRING(std::string &x); inline void WRITE_CHAR(char x); inline void WRITE_CHAR_ARRAY(const char *x);
inline void WRITE_FLOAT(float x); template <typename T> inline void WRITE_DOUBLE(T x); inline void WRITE_VAR(bool x);
inline void WRITE_VAR(short int x); inline void WRITE_VAR(int x); inline void WRITE_VAR(long int x); inline void WRITE_VAR(long long int x);
inline void WRITE_VAR(unsigned short int x); inline void WRITE_VAR(unsigned int x); inline void WRITE_VAR(unsigned long x);
inline void WRITE_VAR(unsigned long long x); inline void WRITE_VAR(char x); inline void WRITE_VAR(const char *x);
inline void WRITE_VAR(std::string &x); inline void WRITE_VAR(float x); inline void WRITE_VAR(double x); inline void WRITE_VAR(long double x);
template<std::size_t N> inline void WRITE_VAR(std::bitset<N> &bit); template<std::size_t N> inline void WRITE_BITSET(std::bitset<N> &bit);
} __FIO__;
#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 ;
}
void upd(int pos, int l , int r, int k, int toSum )
{
soma[pos] += toSum ;
if(l == r) return;
int aux , mid = (l+r)>>1 ;
if( k <= mid )
{
if( !e[pos] ) aux = create() , e[pos] = aux ;
upd(e[pos] , l , mid , k , toSum ) ;
}
else
{
if(!d[pos]) aux = create() , d[pos] = aux ;
upd(d[pos] , mid+1, r, k , toSum ) ;
}
}
int qry(int pos, int l, int r, int k)
{
if(!pos) return 0 ;
if(l == r) return soma[pos] ;
int mid = (l+r)>>1 ;
if( k <= mid ) return qry(e[pos] , l , mid , k ) ;
return soma[ e[pos] ] + qry( d[pos] , mid+1, r, k ) ;
}
};
int N , Q ;
set<pii> intervalos ;
char str[MAXN] , q[MAXN] ;
SegNode tree[MAXN] ;
void upd(int pos, int l, int r, int toSum) {
for(int i = pos ; i <= N ; i+=(i&-i))
{
tree[i].upd(1,1,N+5, l , toSum) ;
tree[i].upd( 1 , 1 , N+5 , r+1, -toSum ) ;
}
}
int qry(int x , int y )
{
int tot = 0 ;
for(int i = x ; i > 0 ; i -= (i&-i)) tot += tree[i].qry(1,1,N+5, y) ;
return tot ;
}
int main()
{
scanf("%d%d", &N , &Q ) ;
scanf("%s", str ) ;
str[N] = '0';
N++;
for(int i = 1 ; i <= N ; i++ )
{
tree[i].create() ;
tree[i].create() ;
}
for(int i = 0 ; i < N ; i++ )
{
int j = i ;
while( j < N && str[j] == '1' ) j++ ;
intervalos.insert( mk(i+1,j+1) ) ;
upd( i+1 , i+1, j+1, -1 ) ;
upd(j+2, 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 = qry(a,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--;
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 ) ;
upd( toInsert.ff, lamp+1, toInsert.ss , -i-1 ) ;
upd(lamp + 1 , lamp+1, toInsert.ss , i+1 ) ;
str[lamp-1] = '1' ;
}
else
{
pii toInsert1 = mk(meContem->ff,lamp) ;
pii toInsert2 = mk(lamp+1, meContem->ss ) ;
upd(toInsert1.ff, toInsert2.ff, toInsert2.ss , i+1 ) ;
upd( toInsert1.ss + 1 , toInsert2.ff, toInsert2.ss , -i-1 ) ;
intervalos.erase( meContem ) ;
intervalos.insert(toInsert1) ;
intervalos.insert(toInsert2) ;
str[lamp-1] = '0' ;
}
}
}
}
#undef lp
#undef sz
#undef all
#undef lp
#undef pb
#undef sz
#undef all
#undef debug
#undef tiii
#undef mkt
#undef pii
#undef mk
#undef ll
#undef ff
#undef ss
inline void FASTIO::ignore() {
if(REMAINING_CHARACTER == true) REMAINING_CHARACTER = false; else READ_CHARACTER = getchar();
}
inline void FASTIO::flush() {
fflush(stdout);
}
// cin modifications
template <typename T>
inline bool FASTIO::READ_INT(T &x) {
x = 0; T sig = 1;
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
while (!isdigit(READ_CHARACTER) && READ_CHARACTER != EOF) sig = (READ_CHARACTER == '-' ? -sig : sig), READ_CHARACTER = getchar();
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
while (isdigit(READ_CHARACTER)) x = x * 10 + READ_CHARACTER - '0', READ_CHARACTER = getchar();
x *= sig; REMAINING_CHARACTER = true;
return true;
}
template <typename T>
inline bool FASTIO::READ_STRING(T &x) {
x = "";
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
REMAINING_CHARACTER = true;
return true;
}
inline bool FASTIO::READ_GETLINE(std::string &x) {
x = "";
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
while ((READ_CHARACTER != '\n' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
REMAINING_CHARACTER = false;
return true;
}
template <typename T>
inline bool FASTIO::READ_CHAR(T &x) {
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
x = READ_CHARACTER; REMAINING_CHARACTER = false;
return true;
}
template<size_t N>
inline bool FASTIO::READ_CHAR_ARRAY(char (&x)[N]) {
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
char *ptr = &x[0];
while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) *ptr++ = READ_CHARACTER, READ_CHARACTER = getchar();
*ptr = '\0', REMAINING_CHARACTER = true;
return true;
}
inline bool FASTIO::READ_CHAR_ARRAY(char*& x) {
std::string y;
if(READ_STRING(y) == false)
return false;
x = new char[(int)y.size() + 1];
strcpy(x, y.c_str());
return true;
}
template <typename T>
inline bool FASTIO::READ_FLOAT(T &x) {
return (scanf("%f", &x) != EOF);
}
template <typename T>
inline bool FASTIO::READ_DOUBLE(T &x) {
double y;
if(scanf("%lf", &y) == EOF) return false;
x = y;
return true;
}
template<std::size_t N>
inline bool FASTIO::READ_BITSET(std::bitset<N> &x) {
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
int i = 0; REMAINING_CHARACTER = true;
while (READ_CHARACTER == '0' || READ_CHARACTER == '1') x[i++] = READ_CHARACTER - '0', READ_CHARACTER = getchar();
return true;
}
inline bool FASTIO::READ_VAR(short int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(long int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(long long int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(unsigned short int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(unsigned int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(unsigned long &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(unsigned long long &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(std::string &x) {
return READ_STRING(x);
}
inline bool FASTIO::READ_VAR(char &x) {
return READ_CHAR(x);
}
template<size_t N>
inline bool FASTIO::READ_VAR(char (&x)[N]) {
return READ_CHAR_ARRAY(x);
}
inline bool FASTIO::READ_VAR(char*& x) {
return READ_CHAR_ARRAY(x);
}
inline bool FASTIO::READ_VAR(float &x) {
return READ_FLOAT(x);
}
inline bool FASTIO::READ_VAR(double &x) {
return READ_DOUBLE(x);
}
inline bool FASTIO::READ_VAR(long double &x) {
return READ_DOUBLE(x);
}
template<std::size_t N>
inline bool FASTIO::READ_VAR(std::bitset<N> &x) {
return READ_BITSET(x);
}
// cout modifications
template <typename T>
inline void FASTIO::WRITE_INT(T x) {
if (x < 0) {putchar('-'); x = -x; }
char writeBuffer[20], *writePtr = writeBuffer;
do {
*writePtr++ = '0' + x % 10;
x /= 10;
}
while (x);
do { putchar(*--writePtr); }
while (writePtr > writeBuffer);
}
inline void FASTIO::WRITE_CHAR(char x) {
putchar(x);
}
inline void FASTIO::WRITE_CHAR_ARRAY(const char *x) {
while(*x != '\0')
putchar(*x++);
}
inline void FASTIO::WRITE_STRING(std::string &x) {
for(char c: x)
putchar(c);
}
inline void FASTIO::WRITE_FLOAT(float x) {
printf("%f", x);
}
template <typename T>
inline void FASTIO::WRITE_DOUBLE(T x) {
printf("%lf", (double)x);
}
template<std::size_t N>
inline void FASTIO::WRITE_BITSET(std::bitset<N> &x) {
for(int i = (int)x.size() - 1; i >= 0; i--)
putchar(x[i] + 48);
}
inline void FASTIO::WRITE_VAR(bool x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(short int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(long int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(long long int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(unsigned short int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(unsigned int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(unsigned long x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(unsigned long long x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(std::string &x) {
WRITE_STRING(x);
}
inline void FASTIO::WRITE_VAR(char x) {
WRITE_CHAR(x);
}
inline void FASTIO::WRITE_VAR(const char *x) {
WRITE_CHAR_ARRAY(x);
}
inline void FASTIO::WRITE_VAR(float x) {
WRITE_FLOAT(x);
}
inline void FASTIO::WRITE_VAR(double x) {
WRITE_DOUBLE(x);
}
inline void FASTIO::WRITE_VAR(long double x) {
WRITE_DOUBLE(x);
}
template<std::size_t N>
inline void FASTIO::WRITE_VAR(std::bitset<N> &x) {
WRITE_BITSET(x);
}
Compilation message
street_lamps.cpp:38: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
38 | #pragma GCC optimization ("unroll-loops")
|
street_lamps.cpp:39: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
39 | #pragma GCC optimization ("O2")
|
street_lamps.cpp: In instantiation of 'void FASTIO::WRITE_INT(T) [with T = bool]':
street_lamps.cpp:460:14: required from here
street_lamps.cpp:419:9: warning: comparison of constant '0' with boolean expression is always false [-Wbool-compare]
419 | if (x < 0) {putchar('-'); x = -x; }
| ~~^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
134 | scanf("%d%d", &N , &Q ) ;
| ~~~~~^~~~~~~~~~~~~~~~~~
street_lamps.cpp:135:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
135 | scanf("%s", str ) ;
| ~~~~~^~~~~~~~~~~~
street_lamps.cpp:165:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
165 | scanf("%s", q ) ;
| ~~~~~^~~~~~~~~~
street_lamps.cpp:171:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
171 | scanf("%d%d", &a, &b );
| ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:187:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
187 | scanf("%d", &lamp ) ;
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
28544 KB |
Output is correct |
| 2 |
Correct |
18 ms |
28544 KB |
Output is correct |
| 3 |
Correct |
17 ms |
28544 KB |
Output is correct |
| 4 |
Correct |
22 ms |
28544 KB |
Output is correct |
| 5 |
Correct |
19 ms |
28544 KB |
Output is correct |
| 6 |
Correct |
19 ms |
28544 KB |
Output is correct |
| 7 |
Correct |
19 ms |
28672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
380 ms |
32796 KB |
Output is correct |
| 2 |
Correct |
498 ms |
33292 KB |
Output is correct |
| 3 |
Correct |
1034 ms |
38648 KB |
Output is correct |
| 4 |
Execution timed out |
5040 ms |
287308 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
29396 KB |
Output is correct |
| 2 |
Correct |
24 ms |
29184 KB |
Output is correct |
| 3 |
Correct |
24 ms |
29144 KB |
Output is correct |
| 4 |
Correct |
21 ms |
28716 KB |
Output is correct |
| 5 |
Execution timed out |
5065 ms |
332676 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
29056 KB |
Output is correct |
| 2 |
Correct |
23 ms |
29056 KB |
Output is correct |
| 3 |
Correct |
25 ms |
29176 KB |
Output is correct |
| 4 |
Correct |
25 ms |
29184 KB |
Output is correct |
| 5 |
Correct |
2457 ms |
247316 KB |
Output is correct |
| 6 |
Correct |
3687 ms |
273912 KB |
Output is correct |
| 7 |
Execution timed out |
5010 ms |
294836 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
20 ms |
28544 KB |
Output is correct |
| 2 |
Correct |
18 ms |
28544 KB |
Output is correct |
| 3 |
Correct |
17 ms |
28544 KB |
Output is correct |
| 4 |
Correct |
22 ms |
28544 KB |
Output is correct |
| 5 |
Correct |
19 ms |
28544 KB |
Output is correct |
| 6 |
Correct |
19 ms |
28544 KB |
Output is correct |
| 7 |
Correct |
19 ms |
28672 KB |
Output is correct |
| 8 |
Correct |
380 ms |
32796 KB |
Output is correct |
| 9 |
Correct |
498 ms |
33292 KB |
Output is correct |
| 10 |
Correct |
1034 ms |
38648 KB |
Output is correct |
| 11 |
Execution timed out |
5040 ms |
287308 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
