#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse4")
using namespace std;
#define X first
#define Y second
#define pb push_back
typedef pair<int, int> ii;
typedef long long ll;
const int maxn = 3e5+5;
int st[4*maxn];
int arr[maxn];
char s[maxn];
int n;
int rng[maxn];
int ask(int i, int j)
{
int res = 0;
for(int x = j; x; x -= x&(-x)) res += rng[x];
for(int x = i-1; x; x -= x&(-x)) res -= rng[x];
return res;
}
void update(int x, int dx)
{
for(; x<= n; x += x&(-x)) rng[x] += dx;
}
int q;
int A[maxn], B[maxn];
struct node
{
int val;
node *left, *right;
node()
{
val = 0;
left = right = NULL;
}
node* getL()
{
if(left == NULL) left = new node();
return left;
}
node* getR()
{
if(right == NULL) right = new node();
return right;
}
void update(int x, int dx, int p = 1, int L = 1, int R = n+1)
{
if(x> R || x< L) return;
if(L == R)
{
val += dx;
// printf("[%d, %d] is %d\n", L, R, val);
return;
}
int M = (L+R)/2;
if(x<= M) getL()->update(x, dx, 2*p, L, (L+R)/2);
else getR()->update(x, dx, 2*p+1, (L+R)/2+1, R);
val = (left?left->val:0)+(right?right->val:0);
// printf("[%d, %d] is %d\n", L, R, val);
}
int ask(int i, int j, int p = 1, int L = 1, int R = n+1)
{
if(i> R || j< L) return 0;
if(i<= L && R<= j)
{
// printf("[%d, %d] is %d\n", L, R, val);
return val;
}
int x = left?left->ask(i, j, 2*p, L, (L+R)/2):0;
int y = right?right->ask(i, j, 2*p+1, (L+R)/2+1, R):0;
return x+y;
}
};
node* ft[maxn];
void updatems(int x, int y, int dx)
{
// printf("go %d %d %d\n", x, y, dx);
for(; x<= n+1; x += x&(-x))
{
ft[x]->update(y, dx);
// printf("update ft[%d] at %d by %d\n", x, y, dx);
}
}
int askms(int x1, int y1, int x2, int y2)
{
int res = 0;
for(int x = x2; x; x -= x&(-x)) res += ft[x]->ask(y1, y2);
// printf("res is %d\n", ft[1]->ask(1, 6));
return res;
}
void updateme(int x1, int y1, int x2, int y2, int dx)
{
updatems(x1, y1, dx);
updatems(x2+1, y1, -dx);
updatems(x1, y2+1, -dx);
updatems(x2+1, y2+1, dx);
}
int ezreal(int x, int y)
{
return askms(1, 1, x, y);
}
bool con(int a, int b)
{
return ask(a, b-1) == b-a;
}
void toggle(int x, int tim, bool upd)
{
int lo = 1, hi = x;
while(lo< hi)
{
int mid = (lo+hi)/2;
if(con(mid, x)) hi = mid;
else lo = mid+1;
}
int L = lo;
lo = x+1, hi = n+1;
while(lo< hi)
{
int mid = (lo+hi+1)/2;
if(con(x+1, mid)) lo = mid;
else hi = mid-1;
}
int R = lo;
if(arr[x])
{
arr[x] = 0;
updateme(L, x+1, x, R, tim);
}
else
{
arr[x] = 1;
updateme(L, x+1, x, R, -tim);
// printf("go %d %d %d %d %d\n", L, x+1, x, R, -tim);
}
update(x, arr[x] == 1?1:-1);
}
int main()
{
scanf("%d %d", &n, &q);
scanf("%s", s+1);
for(int tim = 1; tim<= q; tim++)
{
A[tim] = B[tim] = -1;
char t[10];
scanf("%s", t+1);
if(t[1] == 't')
{
scanf("%d", &A[tim]);
}
else
{
scanf("%d %d", &A[tim], &B[tim]);
}
}
for(int i = 1; i<= n; i++)
{
if(s[i] == '1')
{
update(i, 1);
arr[i] = 1;
}
}
for(int i = 1; i<= n+1; i++) ft[i] = new node();
for(int tim = 1; tim<= q; tim++)
{
if(B[tim] == -1)
{
int x = A[tim];
toggle(x, tim, 1);
continue;
}
int x = A[tim], y = B[tim];
bool cc = con(x, y);
// printf("con = %d\n", ezreal(x, y));
if(cc) printf("%d\n", tim+ezreal(x, y)+1-1);
else printf("%d\n", ezreal(x, y));
}
}
Compilation message
lamp.cpp: In function 'int main()':
lamp.cpp:157:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~~
lamp.cpp:158:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", s+1);
~~~~~^~~~~~~~~~~
lamp.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", t+1);
~~~~~^~~~~~~~~~~
lamp.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[tim]);
~~~~~^~~~~~~~~~~~~~~
lamp.cpp:170:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &A[tim], &B[tim]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
512 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 |
3 ms |
512 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 |
2 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
