#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
int N, Q, ans[300005], state[300005];
map<pii, int> mp;
vector<pair<pii, int>> in[300005], out[300005];
vector<pii> qu[300005];
void insert(int p, int t)
{
auto rter = mp.upper_bound(pii(p, 0));
auto lter = prev(rter);
int l = p, r = p;
if(rter != mp.end() && rter->F.F == p + 1)
{
auto [a, b] = rter->F;
int s = rter->S;
in[a].emplace_back(make_pair(pii(s, t), a));
out[b].emplace_back(make_pair(pii(s, t), a));
r = b;
mp.erase(rter);
}
if(lter->F.S == p - 1)
{
auto [a, b] = lter->F;
int s = lter->S;
in[a].emplace_back(make_pair(pii(s, t), a));
out[b].emplace_back(make_pair(pii(s, t), a));
l = a;
mp.erase(lter);
}
mp[pii(l, r)] = t + 1;
}
void erase(int p, int t)
{
auto iter = prev(mp.lower_bound(pii(p, N + 1)));
auto [a, b] = iter->F;
int s = iter->S;
in[a].emplace_back(make_pair(pii(s, t), a));
out[b].emplace_back(make_pair(pii(s, t), a));
mp.erase(iter);
if(a < p)
mp[pii(a, p - 1)] = t + 1;
if(p < b)
mp[pii(p + 1, b)] = t + 1;
}
struct segTree
{
vector<int> seg, l, r, lazy;
inline int newnode()
{
seg.emplace_back(0);
l.emplace_back(0);
r.emplace_back(0);
lazy.emplace_back(0);
return (int)seg.size() - 1;
}
inline void apply(int val, int i, int L, int R)
{
lazy[i] += val;
seg[i] += val * (R - L + 1);
}
void modify(int mL, int mR, int val, int i = 0, int L = 1, int R = Q)
{
if(mL <= L && R <= mR)
apply(val, i, L, R);
else if(R < mL || mR < L)
return;
else
{
int mid = (L + R) / 2;
if(!l[i]) l[i] = newnode();
if(!r[i]) r[i] = newnode();
apply(lazy[i], l[i], L, mid);
apply(lazy[i], r[i], mid + 1, R);
lazy[i] = 0;
modify(mL, mR, val, l[i], L, mid);
modify(mL, mR, val, r[i], mid + 1, R);
seg[i] = seg[l[i]] + seg[r[i]];
}
}
int query(int mL, int mR, int i = 0, int L = 1, int R = Q)
{
if(mL <= L && R <= mR)
return seg[i];
else if(R < mL || mR < L)
return 0;
else
{
int mid = (L + R) / 2;
if(!l[i]) l[i] = newnode();
if(!r[i]) r[i] = newnode();
apply(lazy[i], l[i], L, mid);
apply(lazy[i], r[i], mid + 1, R);
lazy[i] = 0;
return query(mL, mR, l[i], L, mid) + query(mL, mR, r[i], mid + 1, R);
}
}
} tree[300005];
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
mp[pii(-2, -2)] = -1;
cin >> N >> Q;
for(int i = 1; i <= N; i++)
{
char c;
cin >> c;
state[i] = c - '0';
}
for (int i = 1; i <= N; i++)
if(state[i] == 1)
{
int j = i;
while(state[j + 1])
j++;
mp[pii(i, j)] = 1;
i = j;
}
for (int i = 1; i <= Q; i++)
{
string s;
int a, b;
cin >> s;
if(s == "toggle")
{
ans[i] = -1;
cin >> a;
state[a] ^= 1;
if(state[a])
insert(a, i);
else
erase(a, i);
}
else if(s == "query")
{
cin >> a >> b;
b--;
qu[b].emplace_back(pii(a, i));
}
//for (auto [p, v] : mp)
// cerr << "(" << p.F << ", " << p.S << ") " << v << " ";
//cerr << '\n';
}
mp.erase(mp.begin());
for (auto [p, v] : mp)
{
auto [a, b] = p;
in[a].emplace_back(make_pair(pii(v, Q), a));
}
for (int i = 1; i <= N; i++)
tree[i].newnode();
for (int i = 1; i <= Q; i++)
{
for (auto [p, k] : in[i])
{
auto [l, r] = p;
//cerr << l << ' ' << r << ' ' << k << ' ' << i << '\n';
for (; k <= N; k += (k & -k))
tree[k].modify(l, r, 1);
}
for (auto [r, j] : qu[i])
{
for (; r > 0; r -= (r & -r))
ans[j] += tree[r].query(1, j);
}
for (auto [p, k] : out[i])
{
auto [l, r] = p;
//cerr << l << ' ' << r << ' ' << k << ' ' << i << " out " << '\n';
for (; k <= N; k += (k & -k))
tree[k].modify(l, r, -1);
}
}
for (int i = 1; i <= Q; i++)
if(ans[i] >= 0)
cout << ans[i] << '\n';
}
Compilation message
street_lamps.cpp: In function 'void insert(int, int)':
street_lamps.cpp:22:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
22 | auto [a, b] = rter->F;
| ^
street_lamps.cpp:31:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
31 | auto [a, b] = lter->F;
| ^
street_lamps.cpp: In function 'void erase(int, int)':
street_lamps.cpp:44:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
44 | auto [a, b] = iter->F;
| ^
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:157:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
157 | for (auto [p, v] : mp)
| ^
street_lamps.cpp:159:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
159 | auto [a, b] = p;
| ^
street_lamps.cpp:168:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
168 | for (auto [p, k] : in[i])
| ^
street_lamps.cpp:170:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
170 | auto [l, r] = p;
| ^
street_lamps.cpp:176:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
176 | for (auto [r, j] : qu[i])
| ^
street_lamps.cpp:182:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
182 | for (auto [p, k] : out[i])
| ^
street_lamps.cpp:184:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
184 | auto [l, r] = p;
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
49572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
152 ms |
117104 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
65 ms |
100948 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
100844 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
26 ms |
49572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
