#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
constexpr ll INF = (1LL << 30) - 1LL;
constexpr ll LINF = (1LL << 60) - 1LL;
constexpr ll MOD = 1e9 + 7;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }
struct T {
int a, b, c;
bool operator<(const T &t) const { return a < t.a; }
};
int n, q;
vector<pair<T, int>> v;
vector<int> res;
struct BIT {
vector<ll> dat;
void build(int n) { dat.resize(++n); }
void add(int k, int x) {
for (++k; k < dat.size(); k += k & -k) {
dat[k] += x;
}
}
ll sum(int k) {
ll res = 0;
for (++k; k > 0; k -= k & -k) {
res += dat[k];
}
return res;
}
} bit;
void calc(int l, int r) {
if (r - l <= 1) {
return;
}
int mid = (l + r) / 2;
vector<T> vs;
vector<P> vq;
for (int i = l; i < mid; i++) {
if (v[i].second != -1) {
vs.emplace_back(T{v[i].first.b, v[i].first.c, v[i].second});
}
}
for (int i = mid; i < r; i++) {
if (v[i].second == -1) {
vq.emplace_back(v[i].first.b, v[i].first.c);
}
}
sort(all(vs));
reverse(all(vs));
sort(all(vq));
reverse(all(vq));
int id = 0;
for (int i = 0; i < vq.size(); i++) {
while (id < vs.size() && vq[i].first <= vs[id].a) {
bit.add(vs[id].b, vs[id].c);
id++;
}
res[vq[i].second - 1] += bit.sum(vq[i].second);
}
for (int i = 0; i < id; i++) {
bit.add(vs[i].b, -vs[i].c);
}
calc(l, mid);
calc(mid, r);
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> q;
string s;
cin >> s;
int b = -1;
set<T> st;
for (int i = 0; i < n; i++) {
if (s[i] == '1') {
if (b == -1) {
b = i;
}
} else {
st.insert({b, i - 1, 0});
b = -1;
}
}
if (b != -1) {
st.insert({b, n - 1, 0});
}
res.resize(q, -1);
for (int i = 0; i < q; i++) {
string t;
cin >> t;
int a, b;
if (t == "toggle") {
cin >> a;
--a;
if (s[a] == '1') {
auto it = prev(st.lower_bound({a + 1, -1, -1}));
T p1 = {(*it).a, a - 1, i + 1};
T p2 = {a + 1, (*it).b, i + 1};
v.emplace_back(T{(*it).a, (*it).b, i + 1}, i + 1 - (*it).c);
st.erase(it);
if (p1.a < a) {
st.insert(p1);
}
if (a < p2.b) {
st.insert(p2);
}
} else {
auto ir = st.lower_bound({a + 1, -1, -1});
auto il = prev(ir);
T p = {a, a, i + 1};
if (ir != st.end() && (*ir).a == a + 1) {
v.emplace_back(T{(*ir).a, (*ir).b, i + 1}, i + 1 - (*ir).c);
p.b = (*ir).b;
st.erase(ir);
}
if (ir != st.begin() && (*il).b == a - 1) {
v.emplace_back(T{(*il).a, (*il).b, i + 1}, i + 1 - (*ir).c);
p.a = (*il).a;
st.erase(il);
}
st.insert(p);
}
} else {
cin >> a >> b;
--a;
--b;
res[i] = 0;
if (st.lower_bound({a + 1, -1, -1}) != st.begin()) {
T it = *prev(st.lower_bound({a + 1, -1, -1}));
if (it.b >= b - 1) {
res[i] += i + 1 - it.c;
}
}
v.emplace_back(T{a + 1, b, i + 1}, -1);
}
}
bit.build(q + 10);
sort(all(v));
calc(0, v.size());
for (int i = 0; i < q; i++) {
if (res[i] != -1) {
cout << res[i] << endl;
}
}
}
Compilation message
street_lamps.cpp: In member function 'void BIT::add(int, int)':
street_lamps.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (++k; k < dat.size(); k += k & -k) {
~~^~~~~~~~~~~~
street_lamps.cpp: In function 'void calc(int, int)':
street_lamps.cpp:56:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < vq.size(); i++) {
~~^~~~~~~~~~~
street_lamps.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (id < vs.size() && vq[i].first <= vs[id].a) {
~~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
696 ms |
15620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
4 ms |
468 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
