#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define N 300005
#define INF 0x3f3f3f3f3f3f3f3f
struct Node{
Node *l = NULL, *r = NULL;
int val = 0;
int query(int le, int ri, int x){
if(le == ri) return val;
int m = (le + ri) >> 1;
if(m < x)
return val + (r == NULL ? 0 : r -> query(m + 1, ri, x));
return val + (l == NULL ? 0 : l -> query(le, m, x));
}
void update(int le, int ri, int R, int v){
if(ri <= R){
val += v;
return;
}
int m = (le + ri) >> 1;
if(l == NULL)
l = new Node();
l -> update(le, m, R, v);
if(m < R){
if(r == NULL)
r = new Node();
r -> update(m + 1, ri, R, v);
}
}
} *ans[N << 2];
int n, q;
void update(int id, int l, int r, int L, int R, int val){
if(L <= l && r <= R){
ans[id] -> update(1, n, R, val);
return;
}
if(r < L || l > R){
return;
}
int m = (l + r) >> 1;
update(id << 1, l, m, L, R, val);
update(id << 1 | 1, m + 1, r, L, R, val);
}
int query(int id, int l, int r, int x, int a){
if(l == r){
return ans[id] -> query(1, n, a);
}
int m = (l + r) >> 1;
if(m < x)
return ans[id] -> query(1, n, a) + query(id << 1 | 1, m + 1, r, x, a);
return ans[id] -> query(1, n, a) + query(id << 1, l, m, x, a);
}
set<pair<pair<int, int>, int> > s;
int t;
void remove(set<pair<pair<int, int>, int> >::iterator it){
update(1, 1, n, it -> ff.ss, it -> ff.ff, t - it -> ss);
s.erase(it);
}
int st[N];
pair<int, int> tmp;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>q;
tmp.ff = n + 1;
for(int i = 1; i < (n << 2); ++i)
ans[i] = new Node();
for(int i = 1; i <= n; i++){
char c;
cin>>c;
st[i] = c - '0';
if(st[i] == 1){
if(tmp.ff > n)
tmp.ss = i;
tmp.ff = i;
} else {
if(tmp.ff <= n){
s.insert({tmp, 0});
tmp.ff = n + 1;
}
}
}
if(tmp.ss <= n)
s.insert({tmp, 0});
for(t = 1; t <= q; t++){
string q;
int a, b;
cin>>q;
if(q[0] == 'q'){
cin>>a>>b;
b--;
auto it = s.lower_bound({{a, a}, 0});
if(it == s.end())
cout<<query(1, 1, n, a, b)<<'\n';
else
cout<<query(1, 1, n, a, b) + (it -> ff.ss <= a && it -> ff.ff >= b ? t - it -> ss : 0)<<'\n';
} else {
cin>>a;
if(st[a] == 1){
auto it = s.lower_bound({{a, a}, 0});
int le = it -> ff.ss;
int ri = it -> ff.ff;
remove(it);
if(le < a)
s.insert({{a - 1, le}, t});
if(ri > a)
s.insert({{ri, a + 1}, t});
} else {
int ri = a;
int le = a;
if(st[a + 1]){
auto it = s.lower_bound({{a, a}, 0});
ri = it -> ff.ff;
remove(it);
}
if(st[a - 1]){
auto it = --s.lower_bound({{a, a}, 0});
le = it -> ff.ss;
remove(it);
}
s.insert({{ri, le}, t});
}
st[a] ^= 1;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
760 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 |
Incorrect |
179 ms |
1436 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1016 KB |
Output is correct |
| 2 |
Correct |
4 ms |
888 KB |
Output is correct |
| 3 |
Correct |
4 ms |
888 KB |
Output is correct |
| 4 |
Correct |
3 ms |
504 KB |
Output is correct |
| 5 |
Correct |
1771 ms |
311516 KB |
Output is correct |
| 6 |
Correct |
1627 ms |
300908 KB |
Output is correct |
| 7 |
Correct |
1499 ms |
260272 KB |
Output is correct |
| 8 |
Correct |
334 ms |
50652 KB |
Output is correct |
| 9 |
Incorrect |
94 ms |
1144 KB |
Output isn't correct |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
632 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
