#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
#define ins insert
struct FT{
vector<int> bit;
int n;
void init(int ns){
n = ns;
bit.resize(n + 1);
}
int get(int v){
int out = 0;
while (v > 0){
out += bit[v];
v = (v & (v + 1)) - 1;
}
return out;
}
void upd(int v, int k){
while (v <= n){
bit[v] += k;
v |= (v + 1);
}
}
void updr(int l, int r, int k){
upd(l, k);
upd(r + 1, -k);
}
};
struct ST{
struct node{
vector<int> x;
map<int, int> mp;
FT T;
};
vector<node> t;
int n;
ST(int ns){
n = ns;
t.resize(4 * n);
for (int i = 1; i < t.size(); i++){
t[i].x.pb(0);
}
}
vector<int> :: iterator it;
void upd(int v, int tl, int tr, int& l, int& r, int& x){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
it = upper_bound(t[v].x.begin(), t[v].x.end(), r);
if (it == t[v].x.begin()) return;
it--;
int i = (int) (it - t[v].x.begin()) + 1;
t[v].T.updr(1, i, x);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
upd(vv, tl, tm, l, r, x);
upd(vv + 1, tm + 1, tr, l, r, x);
}
void upd(int l, int r, int x){
upd(1, 1, n, l, r, x);
}
int get(int v, int tl, int tr, int& l, int& i){
int out = t[v].T.get(t[v].mp[i]);
if (tl == tr){
return out;
}
int tm = (tl + tr) / 2, vv = 2 * v;
if (l <= tm){
return out + get(vv, tl, tm, l, i);
}
return out + get(vv + 1, tm + 1, tr, l, i);
}
int get(int l, int i){
return get(1, 1, n, l, i);
}
void add(int v, int tl, int tr, int& l, int& r, int& i){
t[v].x.pb(r);
t[v].mp[i] = (int) t[v].x.size() - 1;
if (tl == tr) return;
int tm = (tl + tr) / 2, vv = 2 * v;
if (l <= tm){
add(vv, tl, tm, l, r, i);
}
else {
add(vv + 1, tm + 1, tr, l, r, i);
}
}
void add(int l, int r, int i){
add(1, 1, n, l, r, i);
}
void build(){
for (int i = 1; i < t.size(); i++){
t[i].T.init((int) t[i].x.size() - 1);
}
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q; cin>>n>>q;
string s; cin>>s; s = '#' + s;
vector<pii> qs = {{}};
vector<int> rr;
for (int qq = 1; qq <= q; qq++){
string type; cin>>type;
if (type == "toggle"){
int k; cin>>k;
qs.pb({k, 0});
}
else {
int l, r; cin>>l>>r;
qs.pb({l, --r});
rr.pb(qq);
}
}
auto cmp = [&](int i, int j){
if (qs[i].ff == qs[j].ff){
return qs[i].ss < qs[j].ss;
}
return qs[i].ff < qs[j].ff;
};
sort(rr.begin(), rr.end(), cmp);
ST T(n);
for (int i: rr){
T.add(qs[i].ff, qs[i].ss, i);
}
T.build();
set<pii> st;
int i = 1;
while (i <= n){
if (s[i] == '0'){
i++;
continue;
}
int j = i;
while (j <= n && s[j] == '1'){
j++;
}
st.ins({i, j - 1});
i = j;
}
for (int i = 1; i <= q; i++){
auto& [a, b] = qs[i];
if (!b){
if (s[a] == '0'){
auto it = st.ins({a, a}).ff;
vector<pii> add;
if (it != st.begin()){
auto it1 = prev(it);
auto [l, r] = *it1;
if (r == (a - 1)){
add.pb({l, a});
}
}
if (it != prev(st.end())){
auto it1 = next(it);
auto [l, r] = *it1;
if (l == (a + 1)){
add.pb({a, r});
}
}
if (add.size() == 2){
st.erase(it);
pii R = {add[0].ff, add[1].ss};
T.upd(R.ff, R.ss, -i);
st.ins(R);
}
else if (add.size() == 1){
st.erase(it);
pii R = {add[0].ff, add[0].ss};
T.upd(R.ff, R.ss, -i);
st.ins(R);
}
s[a] = '1';
}
else {
auto it = st.lower_bound({a + 1, 0}); it--;
auto [l, r] = *it;
T.upd(l, r, i); // [..., i]
st.erase(it);
if (l < a) st.ins({l, a - 1});
if (a < r) st.ins({a + 1, r});
s[a] = '0';
}
}
else {
int out = T.get(qs[i].ff, i);
auto it = st.lower_bound({a + 1, 0});
if (it != st.begin()){
it--;
if ((*it).ff <= a && b <= (*it).ss){
out += i;
}
}
cout<<out<<"\n";
}
}
}
Compilation message
street_lamps.cpp: In constructor 'ST::ST(int)':
street_lamps.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ST::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for (int i = 1; i < t.size(); i++){
| ~~^~~~~~~~~~
street_lamps.cpp: In member function 'void ST::build()':
street_lamps.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ST::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
100 | for (int i = 1; i < t.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
699 ms |
72020 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
1628 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
