#include <bits/stdc++.h>
//#include "bits_stdc++.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%lld", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define FOR(i, x, n) for (ll i =x; i<=n; ++i)
#define RFOR(i, x, n) for (ll i =x; i>=n; --i)
using namespace std;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;
ll n, q, a, b;
ll MAXN = 300005;
struct qq
{
ll type, l, r, t;
qq(ll a, ll b, ll c, ll d) {type = a, l = b, r = c, t= d;}
};
struct range
{
ll l, r, t;
range(ll a, ll b, ll c) {l = a, r = b, t = c;}
bool operator< (const range & other) const
{
if (l!=other.l) return l< other.l;
return r < other.r;
}
};
bool compare(qq a, qq b)
{
return a.l < b.l;
}
// BIT
vector<ll> fenwick(MAXN,0);
ll ps(ll i)
{
if (i==0) return 0;
ll sum=0;
while (i>0)
{
sum+=fenwick[i];
i-=i&(-i);
}
return sum;
}
void update(ll i, ll v)
{
while (i<n+2)
{
fenwick[i]+=v;
i+=i&(-i);
}
}
ll query(ll l, ll r)
{
if (l>r) return 0;
return ps(r) - ps(l-1);
}
vector<qq> que[300005];
ll state[300005], ans[300005];
string s;
void dnc(ll from, ll to)
{
if (from >= to) return;
ll mid = (from+to)/2;
vector<qq> cur;
for (ll i=from; i<=mid; ++i) for (qq u: que[i]) if (u.type==0) cur.pb(u);
for (ll i=mid+1; i<=to; ++i) for (qq u: que[i]) if (u.type) cur.pb(u);
sort(all(cur), compare);
for (qq u: cur)
{
if (u.type==0) update(u.r, u.t);
else ans[u.t] += query(u.r, n);
}
for (qq u: cur) if (u.type==0) update(u.r, -u.t);
dnc(from, mid); dnc(mid+1, to);
}
int main()
{
input2(n, q);
cin >> s;
ll l = LLONG_MAX;
set<range> ds;
for (ll i=1; i<=n; ++i)
{
state[i] = s[i-1]-'0';
if (l==LLONG_MAX && state[i]) l = i;
if (state[i]==0) {if (l<i) ds.insert(range(l, i-1, 0)); l = LLONG_MAX;}
else if (i==n) {if (l<=i) ds.insert(range(l, i, 0)); l = LLONG_MAX;}
}
//for (range x: ds) show3(x.l, x.r, x.t);
fill(ans, ans+q+1, -1);
for (ll i=1; i<=q; ++i)
{
//show(i);
cin >> s;
//show(s);
if (s=="toggle")
{
input(a);
if (state[a]) // turn off
{
range it = *(--ds.lb(range(a+1, -1LL, 0)));
que[i].pb(qq(0, it.l, it.r, i - it.t));
ds.erase(--ds.lb(range(a+1, -1LL, 0)));
if (it.l < a)ds.insert(range(it.l, a-1, i));
if (it.r > a) ds.insert(range(a+1, it.r, i));
}
else // turn on
{
ll nowl = a, nowr = a;
auto it = ds.lb(range(a+1, -1LL, 0));
if (it!=ds.begin() && prev(it)->r == a-1)
{
--it;
nowl = it->l;
que[i].pb(qq(0, it->l, it->r, i-it->t));
it = ds.erase(it);
}
if (it!=ds.end() && it->l <= a+1)
{
nowr = it->r;
que[i].pb(qq(0, it->l, it->r, i-it->t));
ds.erase(it);
}
ds.insert(range(nowl, nowr, i));
}
state[a] = !state[a];
}
else
{
input2(a, b);
b--;
ans[i] = 0;
auto it = ds.lb(range(a+1, -1LL, 0));
//show(1);
if (it!=ds.begin() && prev(it)-> r >= b && prev(it)->l <= a) ans[i] = i - prev(it)->t;
//show(1);
//show(ans[i]);
que[i].pb(qq(1, a, b, i));
}
}
//for (ll i=1; i<=q; ++i) {show(i); for (qq u: que[i]) show3(u.l, u.r, u.t);}
dnc(0, q);
for (ll i=1; i<=q; ++i) if (ans[i]!=-1) print(ans[i], '\n');
return 0;
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:118:2: note: in expansion of macro 'input2'
118 | input2(n, q);
| ^~~~~~
street_lamps.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%lld", &x);
| ~~~~~^~~~~~~~~~~~
street_lamps.cpp:138:4: note: in expansion of macro 'input'
138 | input(a);
| ^~~~~
street_lamps.cpp:13:27: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | #define input2(x, y) scanf("%lld%lld", &x, &y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:172:4: note: in expansion of macro 'input2'
172 | input2(a, b);
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
424 ms |
42564 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9820 KB |
Output is correct |
| 2 |
Correct |
6 ms |
9796 KB |
Output is correct |
| 3 |
Incorrect |
6 ms |
9820 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9820 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
9940 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9816 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
