#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 Node1
{
pll val;
Node1 *lc, *rc;
Node1() : lc(NULL), rc(NULL) {}
};
struct Node2
{
Node1 *val;
Node2 *lc, *rc;
Node2() : val(NULL), lc(NULL), rc(NULL) {}
};
void update1(Node1 *node, int tl, int tr, int x, pll val)
{
node->val=node->val+val;
if(tl==tr) return;
int mid=tl+tr>>1;
if(x<=mid)
{
if(node->lc==NULL) node->lc=new Node1();
update1(node->lc, tl, mid, x, val);
}
else
{
if(node->rc==NULL) node->rc=new Node1();
update1(node->rc, mid+1, tr, x, val);
}
}
pll query1(Node1 *node, int tl, int tr, int l, int r)
{
if(tr<l || r<tl) return pll(0, 0);
if(l<=tl && tr<=r) return node->val;
int mid=tl+tr>>1;
pll ret(0, 0);
if(node->lc!=NULL) ret=ret+query1(node->lc, tl, mid, l, r);
if(node->rc!=NULL) ret=ret+query1(node->rc, mid+1, tr, l, r);
return ret;
}
void update2(Node2 *node, int tl, int tr, int y, int x, pll val)
{
if(node->val==NULL) node->val=new Node1();
update1(node->val, 1, N, x, val);
if(tl==tr) return;
int mid=tl+tr>>1;
if(y<=mid)
{
if(node->lc==NULL) node->lc=new Node2();
update2(node->lc, tl, mid, y, x, val);
}
else
{
if(node->rc==NULL) node->rc=new Node2();
update2(node->rc, mid+1, tr, y, x, val);
}
}
pll query2(Node2 *node, int tl, int tr, int yl, int yr, int xl, int xr)
{
if(yr<tl || tr<yl) return pll(0, 0);
if(yl<=tl && tr<=yr) return query1(node->val, 1, N, xl, xr);
int mid=tl+tr>>1;
pll ret(0, 0);
if(node->lc!=NULL) ret=ret+query2(node->lc, tl, mid, yl, yr, xl, xr);
if(node->rc!=NULL) ret=ret+query2(node->rc, mid+1, tr, yl, yr, xl, xr);
return ret;
}
Node2 *root=new Node2();
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++) update2(root, 1, N, *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())
{
update2(root, 1, N, range(a-1).second, range(a-1).first, pll(-(Q-i+1), -1));
update2(root, 1, N, 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())
{
update2(root, 1, N, 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())
{
update2(root, 1, N, 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);
}
update2(root, 1, N, range(a).second, range(a).first, pll((Q-i+1), 1));
A[a]=1;
}
else
{
int s, e;
tie(s, e)=range(a);
update2(root, 1, N, 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);
update2(root, 1, N, range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
}
else if(e==a)
{
E.erase(a);
E.insert(a-1);
update2(root, 1, N, range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
}
else
{
S.insert(a+1);
E.insert(a-1);
update2(root, 1, N, range(a-1).second, range(a-1).first, pll((Q-i+1), 1));
update2(root, 1, N, range(a+1).second, range(a+1).first, pll((Q-i+1), 1));
}
A[a]=0;
}
}
else
{
scanf("%d%d", &a, &b); b--;
pll ret=query2(root, 1, N, b, N, 1, a);
printf("%lld\n", ret.first-ret.second*(Q-i+1));
}
}
}
Compilation message
street_lamps.cpp: In function 'void update1(Node1*, int, int, int, pll)':
street_lamps.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
street_lamps.cpp: In function 'pll query1(Node1*, int, int, int, int)':
street_lamps.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
street_lamps.cpp: In function 'void update2(Node2*, int, int, int, int, pll)':
street_lamps.cpp:64:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
street_lamps.cpp: In function 'pll query2(Node2*, int, int, int, int, int, int)':
street_lamps.cpp:81:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int mid=tl+tr>>1;
~~^~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:92:12: warning: unused variable 'j' [-Wunused-variable]
int i, j;
^
street_lamps.cpp:94: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:95: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:108:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", st);
~~~~~^~~~~~~~~~
street_lamps.cpp:111:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &a);
~~~~~^~~~~~~~~~
street_lamps.cpp:177: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 |
Correct |
377 ms |
4876 KB |
Output is correct |
| 2 |
Correct |
530 ms |
5812 KB |
Output is correct |
| 3 |
Correct |
1399 ms |
22820 KB |
Output is correct |
| 4 |
Runtime error |
1406 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1912 KB |
Output is correct |
| 2 |
Correct |
7 ms |
1912 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1656 KB |
Output is correct |
| 4 |
Correct |
2 ms |
380 KB |
Output is correct |
| 5 |
Runtime error |
2106 ms |
524288 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1144 KB |
Output is correct |
| 2 |
Correct |
5 ms |
1532 KB |
Output is correct |
| 3 |
Correct |
6 ms |
1784 KB |
Output is correct |
| 4 |
Correct |
8 ms |
1912 KB |
Output is correct |
| 5 |
Correct |
1493 ms |
493196 KB |
Output is correct |
| 6 |
Runtime error |
1235 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 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 |
Correct |
377 ms |
4876 KB |
Output is correct |
| 9 |
Correct |
530 ms |
5812 KB |
Output is correct |
| 10 |
Correct |
1399 ms |
22820 KB |
Output is correct |
| 11 |
Runtime error |
1406 ms |
524292 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 12 |
Halted |
0 ms |
0 KB |
- |
