#include <bits/stdc++.h>
using namespace std;
int n;
char state[300005];
set<int> setBlock[300005];
vector<int> vectorBlock[300005];
vector<int> FT[300005];
/**
* Build the (compressed) fenwick tree
*/
void build(int l, int r){
for(int i = l; i > 0; i -= i & -i){
for(int j = r; j > 0; j -= r & -r){
setBlock[i].insert(j);
}
}
}
void finalizeBuild(int n){
for(int i = 1; i <= n; i++){
for(int x : setBlock[i]){
vectorBlock[i].push_back(x);
FT[i].push_back(0);
}
FT[i].push_back(0);
}
}
void add(int l, int r, int x){
for(int i = l; i < 300005; i += i & -i){
int st = lower_bound(vectorBlock[i].begin(), vectorBlock[i].end(), r) - vectorBlock[i].begin() + 1;
for(int j = st; j <= vectorBlock[i].size(); j += j & -j){
FT[i][j] += x;
}
}
}
int sum(int l, int r){
int ret = 0;
for(int i = l; i > 0; i -= i & -i){
int st = lower_bound(vectorBlock[i].begin(), vectorBlock[i].end(), r) - vectorBlock[i].begin() + 1;
assert(vectorBlock[i][st-1] == r);
for(int j = st; j > 0; j -= j & -j){
ret += FT[i][j];
}
}
return ret;
}
vector<tuple<char,int,int> > queries;
int qidx;
/**
* Returns the queries index i where i-th query is toggle something in range l, r
* Complexity: O(log N)
* Seems like requires a segment tree (?)
*/
int lastToggle(int l, int r){
// Try O(N) first
/// @TODO: opt to O(log N)
for(int i = qidx; i >= 0; i--){
int idx = get<1>(queries[i]);
if(get<0>(queries[i]) == 'q') continue;
if(l <= idx && idx <= r) return i;
}
return -1;
}
/**
* Find rightmost i such that state[i] == 0 but i < x or returns 0 if not exists
* Complexity: O(log N)
* Requires descent on fenwick tree
*/
int getRightmostZero(int x){
// Try O(N) first
/// @TODO: opt to O(log N)
for(int i = x-1; i > 0; i--){
if(state[i] == '0') return i;
}
return 0;
}
/**
* Find leftmost i such that state[i] == 0 but i > x or returns n+1 if not exists
* Complexity: O(log N)
* Requires descent on fenwick tree
*/
int getLeftmostZero(int x){
// Try O(N) first
/// @TODO: opt to O(log N)
for(int i = x+1; i <= n; i++){
if(state[i] == '0') return i;
}
return n+1;
}
/**
* Returns whether there are some zeroes in the range l, r ?
* Complexity: O(log N)
* Requires another fenwick tree
*/
bool hasZero(int l, int r){
return getLeftmostZero(l-1) <= r;
}
int query(int l, int r){
if(!hasZero(l, r)){
// if all l -- r is 1,
return sum(l,r) + qidx - lastToggle(l, r);
}else{
// elif some l -- r is 0
return sum(l, r);
}
}
void toggle(int i){
int l = getRightmostZero(i);
int r = getLeftmostZero(i);
if(state[i] == '1'){
// toggle 1 to 0: find rightmost left 0, leftmost right 0
// let them be l, r
// (all subintervals) stats[l+1][r-1] += i - lastToggle(l, r)
int d = i - lastToggle(l, r);
add(l+1, 1, d);
add(l+1, r, -d);
}else{
// toggle 0 to 1: find rightmost left 0, leftmost right 0
// let them be l, r
// (all subintervals) stats[l+1][i-1] += i - lastToggle(l, i)
// (all subintervals) stats[i+1][r-1] += i - lastToggle(i, r)
int dl = i - lastToggle(l, i);
add(l+1, 1, dl);
add(l+1, i, -dl);
int dr = i - lastToggle(i, r);
add(i+1, 1, dr);
add(i+1, r, -dr);
}
state[i] = '0'+'1'-state[i];
}
int main(){
int q;
scanf("%d%d",&n,&q);
scanf("%s", state+1);
for(int i = 0; i < q; i++){
char str[32];
int l, r = 0;
scanf("%s%d",str,&l);
if(str[0] == 'q') scanf("%d",&r);
r--;
queries.emplace_back(str[0], l, r);
if(str[0] == 'q') build(l, r);
}
finalizeBuild(n);
for(qidx = 0; qidx < q; qidx++){
char c; int l, r;
tie(c, l, r) = queries[qidx];
if(c == 'q'){
printf("%d\n", query(l, r));
}else{
toggle(l);
}
}
}
Compilation message
street_lamps.cpp: In function 'void add(int, int, int)':
street_lamps.cpp:30:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int j = st; j <= vectorBlock[i].size(); j += j & -j){
| ~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:132:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
132 | scanf("%d%d",&n,&q);
| ~~~~~^~~~~~~~~~~~~~
street_lamps.cpp:133:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
133 | scanf("%s", state+1);
| ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:137:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
137 | scanf("%s%d",str,&l);
| ~~~~~^~~~~~~~~~~~~~~
street_lamps.cpp:138:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
138 | if(str[0] == 'q') scanf("%d",&r);
| ~~~~~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
28544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
779 ms |
38144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
21 ms |
29056 KB |
Output is correct |
| 2 |
Incorrect |
83 ms |
42976 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
177 ms |
55672 KB |
Output is correct |
| 2 |
Incorrect |
144 ms |
51320 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
19 ms |
28544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
