//Never stop trying
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
typedef string str;
typedef long long ll;
typedef double db;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<str> vs;
typedef vector<ld> vd;
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
const int MOD = 1e9 + 7; //998244353
const ll INF = 1e18;
const int MX = 3e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up
template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))
#define dbg(x) cerr << " - " << #x << " : " << x << endl;
#define dbgs(x,y) cerr << " - " << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << " - " << #v << " : " << endl << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
void IO() {
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int N,Q; str s;
V<pair<int,pi>> q;
bool cmp(pair<pi,pi> a, pair<pi,pi> b){
if(a.fi.fi!=b.fi.fi) return a.fi.fi < b.fi.fi;
return a.se.se < b.se.se;
}
vi bit(MX,0);
void add(int i, int v){
i++;
for(;i<MX;i+=i&-i) bit[i]+=v;
}
int getSum(int i){
int ans=0;
for(;i;i-=i&-i) ans+=bit[i];
return ans;
}
int getSumRange(int l, int r){
l++; r++;
return getSum(r)-getSum(l-1);
}
vi number(MX,0);
void updateNumber(int i,int v){
i++;
for(;i<MX;i+=i&-i) number[i]+=v;
}
int getNum(int i){
int ans=0;
for(;i;i-=i&-i) ans+=number[i];
return ans;
}
int getNumber(int l, int r){
r++; l++;
return getNum(r)-getNum(l-1);
}
vi rmv(MX,0);
void updateToRemove(int i,int v){
i++;
for(;i<MX;i+=i&-i) rmv[i]+=v;
}
int getRmv(int i){
int ans=0;
for(;i;i-=i&-i) ans+=rmv[i];
return ans;
}
int getToRemove(int l, int r){
r++; l++;
return getRmv(r)-getRmv(l-1);
}
vi closed(MX,0);
void updateClosed(int i,int v){
i++;
for(;i<MX;i+=i&-i) closed[i]+=v;
}
int getCl(int i){
int ans=0;
for(;i;i-=i&-i) ans+=closed[i];
return ans;
}
int getClosed(int l, int r){
r++; l++;
return getCl(r)-getCl(l-1);
}
int main() {
boost;
cin>>N>>Q;
cin>>s;
FOR(i,0,Q){
str t; cin>>t;
if(t=="toggle"){
int i; cin>>i; i--;
q.pb({0,{i,-1}});
}
else{
int i,j; cin>>i>>j; i--; j--;
q.pb({1,{i,j}});
}
}
vi ans;
str ss=s;
FOR(i,0,N) if(s[i]=='1') add(i,1);
pi a[N]; //{right of the interval, moment it opened}
FOR(i,0,N) a[i]={-1,-1};
int cnt=0;
FOR(i,0,sz(ss)){
if(s[i]=='1') cnt++;
if(s[i]=='0' || i==N-1){
if(cnt>0){
int x=(i==N-1 && s[i]=='1');
int l=i-cnt+x,r=i-1+x;
a[l]={r,0};
}
cnt=0;
}
}
//FOR(i,0,N) cout << a[i].fi << ' ' << a[i].se << endl;
V<pair<pi,int>> vec; //closed intervals and their duration
int i=0;
for(;i<Q;i++){
if(q[i].fi==1) break;
int idx=q[i].se.fi;
int l=idx,r=idx;
int ll=0,rr=idx-1;
while(ll<=rr){
int m=(ll+rr)/2;
if(getSumRange(m,idx-1)==idx-m){
l=m; rr=m-1;
}
else ll=m+1;
}
ll=idx+1,rr=N-1;
while(ll<=rr){
int m=(ll+rr)/2;
if(getSumRange(idx+1,m)==m-idx){
r=m; ll=m+1;
}
else rr=m-1;
}
//cout << l << ' ' << r << endl;
if(ss[idx]=='1'){ //111 1 111 --> 111 0 111
vec.pb({{l,r},i+1-a[l].se});
a[l]={-1,-1};
if(l!=idx){
a[l]={idx-1,i+1};
}
if(r!=idx){
a[idx+1]={r,i+1};
}
add(idx,-1);
ss[idx]='0';
}
else{ //111 0 111 --> 1111111
if(l!=idx){
vec.pb({{l,idx-1},i+1-a[l].se});
a[l]={-1,-1};
}
if(r!=idx){
vec.pb({{idx+1,r},i+1-a[idx+1].se});
a[idx+1]={-1,-1};
}
a[l]={r,i+1};
add(idx,1);
ss[idx]='1';
}
}
//for(auto x: vec) cout << x.fi.fi << ' ' << x.fi.se << ' ' << x.se << endl;
//FOR(i,0,N) cout << a[i].fi << ' ' << a[i].se << endl;
V<pair<pi,pi>> v; //closed intervals + opened intervals
//+ queries
for(auto x: vec){
v.pb({x.fi,{x.se,0}});
}
FOR(i,0,N) if(a[i].fi!=-1){
v.pb({{i,a[i].fi},{a[i].se,1}});
}
for(;i<Q; i++){
v.pb({{q[i].se.fi,q[i].se.se},{i,2}});
}
sort(all(v),cmp);
/*for(auto x: v){
cout << x.fi.fi << ' ' << x.fi.se << ' '
<< x.se.fi << ' ' << x.se.se << endl;
}*/
vpi res; //{idx,ans};
for(auto x: v){
if(x.se.se==2){
int idx=x.se.fi;
int l=x.fi.fi,r=x.fi.se-1;
//still open
int val=(idx+1)*(getNumber(r,N-1)) - getToRemove(r,N-1);
//closed
val+=getClosed(r,N-1);
res.pb({idx,val});
}
else if(x.se.se==0){
int r=x.fi.se; int val=x.se.fi;
updateClosed(r,val);
}
else{
int r=x.fi.se; int idx=x.se.fi;
updateNumber(r,1);
updateToRemove(r,idx);
}
}
sort(all(res));
for(auto x: res) ans.pb(x.se);
for(auto x: ans) cout << x << ' ' << endl;
return 0;
}
/* Careful!!!
.Array bounds
.Infinite loops
.Uninitialized variables / empty containers
.Order of input
Some insights:
.Binary search
.Graph representation
.Write brute force code
.Change your approach
*/
Compilation message
street_lamps.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
3 | #pragma GCC optimization ("O3")
|
street_lamps.cpp:4: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
4 | #pragma GCC optimization ("unroll-loops")
|
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:249:8: warning: unused variable 'l' [-Wunused-variable]
249 | int l=x.fi.fi,r=x.fi.se-1;
| ^
street_lamps.cpp: In function 'void IO()':
street_lamps.cpp:49:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
49 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:50:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
50 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
10112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
142 ms |
35152 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
12 ms |
10112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
5152 KB |
Output is correct |
| 2 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 3 |
Correct |
4 ms |
5120 KB |
Output is correct |
| 4 |
Correct |
5 ms |
5120 KB |
Output is correct |
| 5 |
Correct |
276 ms |
24808 KB |
Output is correct |
| 6 |
Correct |
338 ms |
25460 KB |
Output is correct |
| 7 |
Correct |
413 ms |
27000 KB |
Output is correct |
| 8 |
Correct |
503 ms |
29104 KB |
Output is correct |
| 9 |
Correct |
217 ms |
26076 KB |
Output is correct |
| 10 |
Correct |
192 ms |
25820 KB |
Output is correct |
| 11 |
Correct |
223 ms |
27908 KB |
Output is correct |
| 12 |
Correct |
193 ms |
27228 KB |
Output is correct |
| 13 |
Correct |
221 ms |
27868 KB |
Output is correct |
| 14 |
Correct |
190 ms |
27216 KB |
Output is correct |
| 15 |
Correct |
255 ms |
29820 KB |
Output is correct |
| 16 |
Correct |
266 ms |
30928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
10112 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
