This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("O3")
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
using pii = pair<int, int>;
int ans[300005];
bool last[300005];
struct State
{
bool type; //0:update, 1:query
int i, a, b;
};
int N, Q;
State state[300005];
bool cur[300005];
set<pii> st;
const int sz = 1 << 19;
int tree[1<<19];
void upd(int id, int v)
{
for (int i = id; i < sz; i += i&-i) {
tree[i] += v;
}
}
int query(int id)
{
int ret = 0;
for (int i = id; i; i -= i&-i) {
ret += tree[i];
}
return ret;
}
bool is_connected(int a, int b)
{
if (st.empty()) return false;
auto it = st.lower_bound({a+1, 0});
if (it == st.begin()) return false;
--it;
return b <= (*it).second;
}
vector<pair<pii, int>> lst[300005];
void open(int t, int i)
{
cur[i] = true;
auto it = st.lower_bound({i+1, 0});
auto it2 = it;
int lft = -1, rht = -1;
if (it == st.end() || (*it).first != i+1) rht = i;
else rht = (*it).second;
if (it == st.begin()) lft = i;
else {
--it;
if ((*it).second != i-1) lft = i;
else lft = (*it).first;
}
auto it3 = it2;
if (it3 != st.begin()) {
--it3;
if ((*it3).second == i-1) st.erase(it3);
}
if (it2 != st.end() && (*it2).first == i+1) st.erase(it2);
st.insert({lft, rht});
lst[t].push_back({{lft, i-1}, -(Q-t)});
lst[t].push_back({{i+1, rht}, -(Q-t)});
lst[t].push_back({{lft, rht}, (Q-t)});
}
void close(int t, int i)
{
cur[i] = false;
auto it = st.lower_bound({i+1, 0});
--it;
int lft = (*it).first, rht = (*it).second;
st.erase(it);
if (lft <= i-1) st.insert({lft, i-1});
if (i+1 <= rht) st.insert({i+1, rht});
lst[t].push_back({{lft, rht}, -(Q-t)});
lst[t].push_back({{lft, i-1}, Q-t});
lst[t].push_back({{i+1, rht}, Q-t});
}
void dnc(int s, int e)
{
if (s == e) return;
vector<pair<int, pair<int, pii>>> need;
int m = s + e >> 1;
for (int k = s; k <= m; k++) {
for (auto &i:lst[k]) {
need.push_back({i.first.first, {0, {i.first.first, i.second}}});
need.push_back({i.first.first, {0, {i.first.second+1, -i.second}}});
need.push_back({i.first.second+1, {0, {i.first.first, -i.second}}});
need.push_back({i.first.second+1, {0, {i.first.second+1, i.second}}});
}
}
for (int i = m+1; i <= e; i++) {
if (state[i].type == true) {
need.push_back({state[i].a, {1, {state[i].b, i}}});
}
}
sort(need.begin(), need.end());
vector<pair<int, int>> tag;
for (auto &k:need) {
if (k.second.first == 0) {
upd(k.second.second.first, k.second.second.second);
tag.push_back({k.second.second.first, k.second.second.second});
}
else {
ans[k.second.second.second] += query(k.second.second.first);
}
}
for (pair<int, int> &p:tag) upd(p.first, -p.second);
dnc(s, m);
dnc(m+1, e);
}
int lst_cnt[300005];
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> N >> Q;
string s; cin >> s;
for (int i = 1; i <= N; i++) cur[i] = (s[i-1] - '0');
for (int i = 1; i <= N; i++) {
if (!cur[i]) {
lst_cnt[i] = -1;
continue;
}
int s = i;
while (i + 1 <= N && cur[i+1]) ++i;
int e = i;
for (int k = s; k <= e; k++) lst_cnt[k] = e;
st.insert({s, e});
}
for (int i = 1; i <= Q; i++) {
string s; cin >> s;
if (s == "toggle") {
int k; cin >> k;
state[i].type = false;
state[i].i = k;
}
else {
int a, b; cin >> a >> b; b--;
state[i].type = true;
state[i].a = a, state[i].b = b;
if (b <= lst_cnt[a]) ans[i] = Q;
}
}
for (int i = 1; i <= Q; i++) {
if (!state[i].type) {
if (!cur[state[i].i]) open(i, state[i].i);
else close(i, state[i].i);
}
else last[i] = is_connected(state[i].a, state[i].b);
}
dnc(1, Q);
for (int i = 1; i <= Q; i++) {
if (!state[i].type) continue;
if (last[i]) ans[i] -= (Q - i);
cout << ans[i] << '\n';
}
}
Compilation message (stderr)
street_lamps.cpp: In function 'void dnc(int, int)':
street_lamps.cpp:86:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
86 | int m = s + e >> 1;
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |