// #pragma GCC target ("avx,avx2,fma")
// #pragma GCC optimize ("Ofast,inline") // O1 - O2 - O3 - Os - Ofast
// #pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b - 1); i >= (a); --i)
#define trav(a, x) for (auto &a : x)
#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back
#define debug(x) cout << #x << " = " << x << endl
#define umap unordered_map
#define uset unordered_set
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const int INF = 1'000'000'007;
struct Fenwick {
vi ft;
Fenwick(int n) { ft.assign(n+1,0); }
int rsq(int i) {
int sum=0;
for(;i;i-=i&-i) sum+=ft[i];
return sum;
}
int rsq(int i,int j) { return rsq(j)-rsq(i-1); }
void update(int i,int v) {
for(;i<sz(ft);i+=i&-i) ft[i]+=v;
}
};
int n, q;
string state;
map<ii,int> build_intervals;
vector<pair<ii,ii>> intervals;
int ans[300005];
string types[300005];
int queries[300005][2],first_query=INF,last_toggle=-1;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
cin >> n >> q >> state;
state+='0';
rep(i,0,n) {
if(state[i]=='0')continue;
rep(j,i,n+1) if(state[j]=='0') {
build_intervals.insert({{i,j},-1});
i=j;
break;
}
}
rep(i,0,q) {
cin>>types[i];
int vals=1+(types[i]=="query");
rep(j,0,vals) cin>>queries[i][j];
if(types[i]=="query") first_query=min(first_query,i);
else last_toggle=i;
}
if(last_toggle>first_query) return 0;
rep(i,0,first_query) {
int pos=queries[i][0];
int start=pos,stop=pos;
vii rem,add;
if(state[pos]=='0') {
auto it=build_intervals.lower_bound(ii(pos,0));
if(it!=build_intervals.end()&&it->first.first==pos+1) {
stop=it->first.second;
rem.emplace_back(it->first);
}
if(it!=build_intervals.begin()&&(--it)->first.second==pos) {
start=it->first.first;
rem.emplace_back(it->first);
}
add.emplace_back(start,stop);
} else {
auto it=build_intervals.upper_bound(ii(pos,INF));
if(it!=build_intervals.begin()) {
--it;
int lo,hi;
tie(lo,hi)=it->first;
if(pos<hi) {
start=lo;
stop=hi;
if(pos!=hi-1) add.emplace_back(pos+1,hi);
if(pos!=lo) add.emplace_back(lo,pos);
}
}
}
trav(item,rem) {
int lo,hi;
tie(lo,hi)=item;
int last_update=build_intervals[{lo,hi}];
intervals.pb({{lo,0},{hi,i-last_update}});
build_intervals.erase({lo,hi});
}
trav(item,add) {
int lo,hi;
tie(lo,hi)=item;
build_intervals.insert({{lo,hi},i});
}
}
trav(item,build_intervals) {
int lo,hi;
tie(lo,hi)=item.first;
int last_update=build_intervals[{lo,hi}];
intervals.pb({{lo,0},{hi,first_query-last_update}});
}
//debug(first_query);
rep(i,first_query,q) {
rep(j,0,2) queries[i][j]-=1+j;
intervals.pb({{queries[i][0],1},{queries[i][1],i-first_query}});
}
sort(all(intervals));
Fenwick fenwick(n+3);
trav(interval,intervals) {
int lo,type,hi,cnt;
tie(lo,type)=interval.first;
tie(hi,cnt)=interval.second;
++lo; ++hi;
//cout<<"lo = "<<lo<<" hi = "<<hi<<" type = "<<type<<" cnt = "<<cnt<<endl;
if(!type) {
fenwick.update(hi-1,cnt);
} else {
ans[cnt]=fenwick.rsq(hi,n+3);
}
}
rep(i,0,q-first_query) {
auto it=build_intervals.upper_bound(ii(queries[i+first_query][0],INF));
if(it!=build_intervals.begin()) {
--it;
if(it->first.second>queries[i+first_query][1]) ans[i]+=i;
}
cout<<ans[i]<<'\n';
}
return 0;
}
Compilation message
street_lamps.cpp: In member function 'void Fenwick::update(int, int)':
street_lamps.cpp:45:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(;i<sz(ft);i+=i&-i) ft[i]+=v;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
15228 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9812 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
9812 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
