#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 3e5 + 5, mod = 1e9 + 7; // !
int t, tree[4 * N],Q, fw[N],a[N],n,ans[N];
string s;
vector<pii> add[N],q[N];
vector<int> rem[N];
void update(int u,int ind,int l,int r) {
if(l > ind || r < ind) return;
if(l == r) {
tree[u] ^= 1;
return;
}
int mid = (l + r)/2;
update(2 * u,ind,l,mid); update(2 * u + 1,ind,mid + 1, r);
tree[u] = min(tree[2 * u], tree[2 *u + 1]);
}
int getL(int u,int ind,int l,int r) {
if(l > ind) return 0;
if(l == r) {
if(tree[u]) {
return l;
}
return l + 1;
}
int mid = (l + r)/2;
if(r <= ind) {
if(tree[2 * u + 1] == 1) return getL(2 * u, ind, l, mid);
return getL(2 * u + 1,ind,mid + 1, r);
}
int x = getL(2 * u + 1,ind,mid + 1,r);
if(x > mid + 1) return x;
return getL(2 * u, ind, l, mid);
}
int getR(int u,int ind,int l,int r) {
if(r < ind) return n + 1;
if(l == r) {
if(tree[u]) return l;
return l - 1;
}
int mid = (l + r)/2;
if(l >= ind) {
if(tree[2 * u] == 1) return getR(2 * u + 1, ind, mid + 1,r);
return getR(2 * u,ind, l, mid);
}
int x = getR(2 * u,ind,l,mid);
if(x < mid) return x;
return getR(2 * u + 1, ind, mid + 1, r);
}
void upd(int ind,int val) {
for(ind;ind >= 1; ind -= ind & (-ind)) fw[ind] += val;
}
int get(int ind) {
int ans = 0;
for(ind; ind <= n; ind += ind & (-ind)) ans += fw[ind];
return ans;
}
main(){
// All toggle events happen before all query events.
cin >> n >> Q;
cin >> s;
for(int i = 1; i <= n; i++) {
a[i] = s[i - 1] - '0';
if(a[i]) update(1,i,1,n);
cout << a[i] <<" ";
}
cout << endl;
int ind = 0,start = 0;
for(int i = 1; i <= Q; i++) {
string s;
cin >> s;
if(s == "toggle") {
int id;
cin >> id;
update(1,id,1,n);
int l = getL(1,id - 1,1,n);
int r = getR(1,id + 1,1,n);
int f = -1;
if(a[i] == 0) f = 1;
a[id] ^= 1;
add[l].push_back({r, f * i});
if(id + 1 <= r) add[id + 1].push_back({r, f * -i});
if(l <= id - 1) add[l].push_back({id - 1,f * -i});
}
else {
int l,r;
cin >> l >> r;
r--;
if(!start) start = i;
q[l].push_back({r, i});
}
}
for(int i = 1; i <= n; i++) {
for(int j = 0; j < add[i].size(); j++) {
upd(add[i][j].f,add[i][j].s);
rem[add[i][j].f].push_back(add[i][j].s);
}
for(int j = 0; j < q[i].size(); j++) {
ans[q[i][j].s] = get(q[i][j].f);
if(getR(1,i,1,n) + 1 >= q[i][j].s) ans[q[i][j].s] += q[i][j].s;
}
for(int j = 0; j < rem[i].size(); j++) {
upd(i,-rem[i][j]);
}
}
for(int i = start; i <= Q; i++) {
cout << ans[i] <<" ";
}
}
Compilation message
street_lamps.cpp: In function 'void upd(long long int, long long int)':
street_lamps.cpp:55:6: warning: statement has no effect [-Wunused-value]
55 | for(ind;ind >= 1; ind -= ind & (-ind)) fw[ind] += val;
| ^~~
street_lamps.cpp: In function 'long long int get(long long int)':
street_lamps.cpp:59:6: warning: statement has no effect [-Wunused-value]
59 | for(ind; ind <= n; ind += ind & (-ind)) ans += fw[ind];
| ^~~
street_lamps.cpp: At global scope:
street_lamps.cpp:62:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
62 | main(){
| ^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:100:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for(int j = 0; j < add[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
street_lamps.cpp:104:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | for(int j = 0; j < q[i].size(); j++) {
| ~~^~~~~~~~~~~~~
street_lamps.cpp:108:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
108 | for(int j = 0; j < rem[i].size(); j++) {
| ~~^~~~~~~~~~~~~~~
street_lamps.cpp:72:6: warning: unused variable 'ind' [-Wunused-variable]
72 | int ind = 0,start = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
309 ms |
40428 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
21580 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
21444 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
21348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
