#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){
if (l > r) return;
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 it1, it2;
void upd(int v, int tl, int tr, int& l, int& r, int& lr, int& rr, int& x){
if (l > tr || r < tl) return;
if (l <= tl && tr <= r){
it1 = lower_bound(t[v].x.begin(), t[v].x.end(), lr);
it2 = upper_bound(t[v].x.begin(), t[v].x.end(), rr);
if (it1 == it2) return;
it2--;
int l1 = (int) (it1 - t[v].x.begin()), r1 = (int) (it2 - t[v].x.begin());
t[v].T.updr(max(1, l1), r1, x);
return;
}
int tm = (tl + tr) / 2, vv = 2 * v;
upd(vv, tl, tm, l, r, lr, rr, x);
upd(vv + 1, tm + 1, tr, l, r, lr, rr, x);
}
void upd(int l1, int r1, int l2, int r2, int x){
upd(1, 1, n, l1, r1, l2, r2, x);
// cout<<x<<" -> "<<l1<<" "<<r1<<" "<<l2<<" "<<r2<<"\n";
}
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].ss == qs[j].ss){
return qs[i].ff < qs[j].ff;
}
return qs[i].ss < qs[j].ss;
};
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'){
st.ins({a, a});
auto it = st.find({a, a});
vector<pii> add;
if (it != st.begin()){
auto it1 = prev(it);
auto [l, r] = *it1;
if (r == (a - 1)){
add.pb({l, r});
}
}
if (it != prev(st.end())){
auto it1 = next(it);
auto [l, r] = *it1;
if (l == (a + 1)){
add.pb({l, r});
}
}
if (add.size() == 2){
st.erase(it);
for (auto p: add) st.erase(p);
pii R = {add[0].ff, add[1].ss};
T.upd(R.ff, a, a, R.ss, -i);
st.ins(R);
}
else if (add.size() == 1){
st.erase(it);
for (auto p: add) st.erase(p);
pii R = {a, add[0].ss};
T.upd(R.ff, a, a, R.ss, -i);
st.ins(R);
}
else {
T.upd(a, a, a, a, -i);
}
s[a] = '1';
}
else {
auto it = st.lower_bound({a + 1, 0}); it--;
auto [l, r] = *it;
assert(l <= a && a <= r);
T.upd(l, a, a, r, 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);
if (!st.empty()){
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:49:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ST::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (int i = 1; i < t.size(); i++){
| ~~^~~~~~~~~~
street_lamps.cpp: In member function 'void ST::build()':
street_lamps.cpp:103:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<ST::node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
103 | for (int i = 1; i < t.size(); i++){
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
344 ms |
137412 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1116 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
1116 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
1628 KB |
Output is correct |
| 2 |
Runtime error |
3 ms |
2652 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
604 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
