#include<bits/stdc++.h>
/*
#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")*/
#define I inline void
#define S struct
#define vi vector<int>
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std ;
using ll = long long ;
using ld = long double ;
const int N = 1e5 + 7 , mod = 1e9 + 7 ;
const int inf = N ;
// How interesting!
int n , k ;
string s;
int a[N] ;
string tmp[N] ;
int ts ;
int solve(int l , int r){
int ret = 0 ;
int x = r - l + 1;
for(int i = 0 ;i <= ts ; i ++){
// cout<< tmp[i] <<" " ;
ret+= (tmp[i].substr(l , x) == string(x , '1') ) ;
}
// cout<<"-----\n" ;
//if(ts)
// exit(0) ;
return ret ;
}
int bit[N] ;
I add(int pos, int x){
for(pos++ ;pos<N;pos+=pos&-pos)
bit[pos]+=x ;
}
int upto(int x){
x++ ;
int ret = 0 ;
for(;x;x-=x&-x)
ret+=bit[x] ;
return ret ;
}
int get(int l, int r){
return upto(r) - upto(l - 1) ;
}
int solve2(int l ,int r){
int ret = 0 ;
for(int i = 0 ;i <= ts ;i++){
// memset(bit , 0 , sizeof bit) ;
vector<int> cont(n+1 , 0) , cont2(n+1 , 0);
vector<pair<int,int>>v ;
int cnt = 0 ;
if(l == r){
ret += 2 * (tmp[i][l] -'0') ;
continue;
}
for(int j = 0 ;j < n ;j ++){
if(tmp[i][j] == '1'){
if(cnt){
} else{
cont[j]++ ;
}
cnt++ ;
}else{
if(cnt){
v.push_back({ j - cnt , j -1 }) ;
cont[j-1]-- ;
cont2[j-1] ++ ;
}else{
}
cnt = 0 ;
}
}
if(cnt){
v.push_back({n - cnt , n - 1 }) ;
cont[n-1] -- ;
cont2[n-1] ++ ;
}
for(int j = 0 ;j <= l ;j ++){
ret += cont[j] ;
}
for(int j = r ; j < n ;j ++)
ret -= cont[j] ;
int aux = 0 ;
for(int j = 0 ;j <= l ;j ++)
aux += cont[j] ;
for(int j = l + 1 ;j < r ; j ++)
aux += cont2[j] ;
aux /= 2;
int q = 0 ;
ret -= aux ;
for(auto u : v){
if(u.first > l && u.second < r)
continue ;
if(u.first > l && u.first < r)
ret -- ;
if(u.second > l && u.second < r)
q ++ ;
}
}
return ret / 2;
}
int main(){
ios_base::sync_with_stdio(0) ;
cin.tie(0) ;
//freopen("in.in" , "r" , stdin) ;
cin >> n >> k ;
cin >> s ;
tmp[0] = s;
for(int i = 0 ;i < n;i ++)
a[i] = s[i] - '0' ;
for(int i = 0 ;i < k ;i ++){
string t ;
int l , r;
cin >> t ;
if(t == "toggle"){
cin >> l ;
tmp[ts+1] = tmp[ts] ;ts++;
tmp[ts][l-1] = '1' - tmp[ts][l-1] + '0';
a[l] ^=1 ;
} else{
cin >> l >> r;
l-- ; r-=2;
cout<< solve2(l , r) <<"\n";
tmp[ts + 1] = tmp[ts] ; ts ++ ;
}
}
return 0 ;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5035 ms |
5120 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
4480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3252 ms |
4836 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
3456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
