#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e5;
int N, Q, A[MAXN+10];
set<int> S, E;
pii range(int x) { return pii(*(--S.upper_bound(x)), *E.lower_bound(x)); }
pll operator + (const pll &p, const pll &q) { return pll(p.first+q.first, p.second+q.second); }
struct Data
{
int t, y, x; pll val;
bool operator < (const Data &p) const { return x<p.x; }
};
vector<Data> todo;
struct BIT
{
pll tree[MAXN+10];
void update(int i, pll v) { for(; i<=N; i+=(i&-i)) tree[i]=tree[i]+v; }
pll query(int i) { pll ret(0, 0); for(; i>0; i-=(i&-i)) ret=ret+tree[i]; return ret; }
void flush(int i) { for(; i<=N; i+=(i&-i)) tree[i]=pll(0, 0); }
}bit;
void update(int y, int x, pll v) { todo.push_back({0, N-y+1, x, v}); }
void query(int y, int x, ll v) { todo.push_back({1, N-y+1, x, {v, todo.size()}}); }
pll ans[MAXN+10];
void solve(int s, int e)
{
int i, j;
if(s==e)
{
if(todo[s].t)
{
pll ret=ans[s];
printf("%lld\n", ret.first-ret.second*todo[s].val.first);
}
return;
}
int mid=s+e>>1;
solve(s, mid);
vector<Data> A, B;
for(i=s; i<=mid; i++) if(!todo[i].t) A.push_back(todo[i]);
for(i=mid+1; i<=e; i++) if(todo[i].t) B.push_back(todo[i]);
sort(A.begin(), A.end());
sort(B.begin(), B.end());
for(i=0, j=0; i<B.size(); i++)
{
for(; j<A.size() && A[j].x<=B[i].x; j++) bit.update(A[j].y, A[j].val);
ans[B[i].val.second]=ans[B[i].val.second]+bit.query(B[i].y);
}
for(j=0; j<A.size(); j++) bit.flush(A[j].y);
solve(mid+1, e);
}
int main()
{
int i, j;
scanf("%d%d", &N, &Q);
for(i=1; i<=N; i++) scanf("%1d", &A[i]);
set<int>::iterator it, jt;
for(i=1; i<=N; i++) if(A[i-1]==0 && A[i]==1) S.insert(i);
for(i=1; i<=N; i++) if(A[i]==1 && A[i+1]==0) E.insert(i);
for(it=S.begin(), jt=E.begin(); it!=S.end() && jt!=E.end(); it++, jt++) update(*jt, *it, pll(Q+1, 1));
for(i=1; i<=Q; i++)
{
char st[10];
int a, b;
scanf("%s", st);
if(st[0]=='t')
{
scanf("%d", &a);
if(A[a]==0)
{
if(S.find(a+1)!=S.end() && E.find(a-1)!=E.end())
{
update(range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
update(range(a+1).second, range(a+1).first, pll(-(Q-i+1), -1));
S.erase(a+1);
E.erase(a-1);
}
else if(S.find(a+1)!=S.end())
{
update(range(a+1).second, range(a+1).first, pll(-(Q-i+1), -1));
S.erase(a+1);
S.insert(a);
}
else if(E.find(a-1)!=E.end())
{
update(range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
E.erase(a-1);
E.insert(a);
}
else
{
S.insert(a);
E.insert(a);
}
update(range(a).second, range(a).first, pll((Q-i+1), 1));
A[a]=1;
}
else
{
int s, e;
tie(s, e)=range(a);
update(range(a).second, range(a).first, pll(-(Q-i+1), -1));
if(s==e)
{
S.erase(a);
E.erase(a);
}
else if(s==a)
{
S.erase(a);
S.insert(a+1);
update(range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
}
else if(e==a)
{
E.erase(a);
E.insert(a-1);
update(range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
}
else
{
S.insert(a+1);
E.insert(a-1);
update(range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
update(range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
}
A[a]=0;
}
}
else
{
scanf("%d%d", &a, &b); b--;
query(b, a, Q-i+1);
}
}
solve(0, todo.size()-1);
}
Compilation message
street_lamps.cpp: In function 'void solve(int, int)':
street_lamps.cpp:50:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=s+e>>1;
~^~
street_lamps.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0, j=0; i<B.size(); i++)
~^~~~~~~~~
street_lamps.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(; j<A.size() && A[j].x<=B[i].x; j++) bit.update(A[j].y, A[j].val);
~^~~~~~~~~
street_lamps.cpp:65:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0; j<A.size(); j++) bit.flush(A[j].y);
~^~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:72:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
street_lamps.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &N, &Q);
~~~~~^~~~~~~~~~~~~~~~
street_lamps.cpp:75:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1; i<=N; i++) scanf("%1d", &A[i]);
~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", st);
~~~~~^~~~~~~~~~
street_lamps.cpp:91:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
~~~~~^~~~~~~~~~
street_lamps.cpp:157:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b); b--;
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
696 ms |
42160 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
504 KB |
Output is correct |
| 2 |
Correct |
5 ms |
632 KB |
Output is correct |
| 3 |
Correct |
4 ms |
504 KB |
Output is correct |
| 4 |
Correct |
3 ms |
508 KB |
Output is correct |
| 5 |
Incorrect |
1716 ms |
59328 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
504 KB |
Output is correct |
| 2 |
Correct |
4 ms |
632 KB |
Output is correct |
| 3 |
Correct |
4 ms |
632 KB |
Output is correct |
| 4 |
Correct |
5 ms |
632 KB |
Output is correct |
| 5 |
Correct |
676 ms |
45856 KB |
Output is correct |
| 6 |
Incorrect |
1012 ms |
54836 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
2 ms |
376 KB |
Output is correct |
| 5 |
Correct |
2 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
2 ms |
376 KB |
Output is correct |
| 8 |
Incorrect |
696 ms |
42160 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
