#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
void debug_out()
{
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B)
{
cerr << ' ' << A;
debug_out(B...);
}
#ifdef DEBUG
#define time(...) 42
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; }
template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; }
mt19937 rng(time(0));
const int INF32 = 1e9;
const int maxN = 300005;
char a0[maxN];
pii que[maxN];
namespace btrp
{
struct Node
{
int y;
int bg, sz, last_change;
Node *l, *r;
Node() {}
Node(int _bg, int _sz, int _last_change): bg(_bg), sz(_sz), last_change(_last_change), y(rng()), l(0), r(0) {}
};
Node* merge(Node *a, Node *b)
{
if (!a) return b;
if (!b) return a;
if (a->y > b->y)
{
a->r = merge(a->r, b);
return a;
}
else
{
b->l = merge(a, b->l);
return b;
}
}
pair<Node*, Node*> split(Node *t, int x)
{
if (!t) return {0, 0};
if (t->bg < x)
{
auto p = split(t->r, x);
t->r = p.fi;
return {t, p.se};
}
else
{
auto p = split(t->l, x);
t->l = p.se;
return {p.fi, t};
}
}
void add(Node *&t, int bg, int sz, int last_change)
{
auto p = split(t, bg);
t = merge(p.fi, merge(new Node(bg, sz, last_change), p.se));
}
void rem(Node *&t, int x)
{
if (!t) return;
if (t->bg == x)
{
t = merge(t->l, t->r);
return;
}
if (t->bg < x)
rem(t->r, x);
else
rem(t->l, x);
}
pair<pii, int> gt(Node *t, int x)
{
if (!t) return {{INF32, INF32}, INF32};
if (t->bg <= x)
{
auto res = gt(t->r, x);
if (res.fi.fi > x)
return {{t->bg, t->sz}, t->last_change};
else
return res;
}
else
{
return gt(t->l, x);
}
}
void travel(Node *t, vector< pair<pii, int> > &a)
{
if (t)
{
travel(t->l, a);
a.push_back(mp(mp(t->bg, t->sz), t->last_change));
travel(t->r, a);
}
}
}
signed main()
{
#ifdef DEBUG
freopen("in", "r", stdin);
#endif
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
if (0 && n <= 100 && q <= 100)
{
char t[q + 1][n];
memset(t, 0, sizeof(t));
string s;
cin >> s;
for (int i = 0; i < n; ++i) t[0][i] = s[i] - '0';
for (int i = 1; i <= q; ++i)
{
memcpy(t[i], t[i - 1], sizeof(t[i]));
string cmd;
cin >> cmd;
if (cmd == "toggle")
{
int j;
cin >> j;
--j;
t[i][j] ^= 1;
}
else
{
int l, r;
cin >> l >> r;
r -= 2;
l--;
int ans = 0;
for (int u = 0; u < i; ++u)
{
bool ok = true;
for (int j = l; j <= r; ++j)
{
ok &= t[u][j];
}
if (ok) ++ans;
}
cout << ans << '\n';
}
}
exit(0);
}
// normal
string tmp;
cin >> tmp;
for (int i = 0; i < n; ++i) a0[i] = tmp[i] - '0';
bool all_ones = true;
bool toggle_to_one = true;
int last_toggle = -1;
int first_query = -1;
int _a[n];
for (int i = 0; i < n; ++i) _a[i] = a0[i];
for (int t = 1; t <= q; ++t)
{
string cmd;
cin >> cmd;
auto &q = que[t];
if (cmd == "toggle")
{
last_toggle = t;
q.se = -1;
cin >> q.fi;
q.fi--;
int i = q.fi;
_a[i] ^= 1;
toggle_to_one &= _a[i] == 1;
}
else
{
if (first_query == -1) first_query = t;
cin >> q.fi >> q.se;
q.fi--;
q.se -= 2;
all_ones &= q.fi == q.se;
}
}
if (all_ones)
{
int when[n], sum[n];
memset(when, 0, sizeof(when));
memset(sum, 0, sizeof(sum));
for (int t = 1; t <= q; ++t)
{
auto &q = que[t];
if (q.se == -1)
{
int i = q.fi;
if (a0[i] == 0)
{
when[i] = t;
}
else
{
sum[i] += t - when[i];
}
a0[i] ^= 1;
}
else
{
int i = q.fi;
cout << sum[i] + (a0[i] == 1 ? t - when[i] : 0) << '\n';
}
}
exit(0);
}
if (toggle_to_one)
{
int when[n];
for (int i = 0; i < n; ++i)
if (a0[i] == 1)
when[i] = 0;
else
when[i] = INF32;
for (int t = 1; t <= q; ++t)
{
auto &q = que[t];
if (q.se == -1)
{
int i = q.fi;
when[i] = t;
}
}
const int logN = 19;
const int N = 1 << logN;
int sgt[2 * N];
fill(sgt, sgt + 2 * N, -INF32);
for (int i = 0; i < n; ++i)
{
sgt[i + N] = when[i];
}
for (int v = N - 1; v >= 1; --v)
{
sgt[v] = max(sgt[v << 1], sgt[v << 1 | 1]);
}
for (int t = 1; t <= q; ++t)
{
auto &q = que[t];
if (q.se != -1)
{
int l = q.fi;
int r = q.se;
int mx = -1e9;
for (l += N, r += N; l <= r; l >>= 1, r >>= 1)
{
if (l & 1) chkmax(mx, sgt[l++]);
if (~r & 1) chkmax(mx, sgt[r--]);
}
cout << max(0, t - mx) << '\n';
}
}
exit(0);
}
if (first_query == -1)
{
exit(0);
}
if (last_toggle < first_query)
{
btrp::Node* blocks = 0;
int cur_bg = -1, cur_sz = -1;
for (int i = 0; i <= n; ++i)
{
if (i < n && a0[i] == 1)
{
if (i == 0 || a0[i - 1] == 0)
{
cur_bg = i;
cur_sz = 1;
}
else ++cur_sz;
}
else
{
if (cur_bg != -1 && (i == n || i > 0 && a0[i - 1] == 1))
{
btrp::add(blocks, cur_bg, cur_sz, 0);
cur_bg = -1;
}
}
}
auto out_blocks = [&]
{
vector< pair<pii, int> > remaining_blocks;
btrp::travel(blocks, remaining_blocks);
for (auto block : remaining_blocks)
{
int bg = block.fi.fi;
int sz = block.fi.se;
int last_change = block.se;
debug(bg, sz, last_change);
}
};
out_blocks();
vector< pair<pii, int> > S;
for (int t = 1; t <= q; ++t)
{
auto &q = que[t];
if (q.se == -1)
{
int i = q.fi;
if (a0[i] == 0)
{
bool Left = (i > 0 && a0[i - 1] == 1);
bool Right = (i + 1 < n && a0[i + 1] == 1);
if (!Left && !Right)
{
btrp::add(blocks, i, 1, t);
}
if (Left && !Right)
{
auto block = btrp::gt(blocks, i - 1);
int bg = block.fi.fi;
int sz = block.fi.se;
int last_change = block.se;
S.push_back(mp(mp(bg, bg + sz - 1), t - last_change));
btrp::rem(blocks, bg);
btrp::add(blocks, bg, sz + 1, t);
}
if (!Left && Right)
{
auto block = btrp::gt(blocks, i + 1);
int bg = block.fi.fi;
int sz = block.fi.se;
int last_change = block.se;
S.push_back(mp(mp(bg, bg + sz - 1), t - last_change));
btrp::rem(blocks, bg);
btrp::add(blocks, bg - 1, sz + 1, t);
}
if (Left && Right)
{
auto block1 = btrp::gt(blocks, i - 1);
int bg1 = block1.fi.fi;
int sz1 = block1.fi.se;
int last_change1 = block1.se;
S.push_back(mp(mp(bg1, bg1 + sz1 - 1), t - last_change1));
btrp::rem(blocks, bg1);
auto block2 = btrp::gt(blocks, i + 1);
int bg2 = block2.fi.fi;
int sz2 = block2.fi.se;
int last_change2 = block2.se;
S.push_back(mp(mp(bg2, bg2 + sz2 - 1), t - last_change2));
btrp::rem(blocks, bg2);
btrp::add(blocks, bg1, sz1 + 1 + sz2, t);
}
}
else
{
pair<pii, int> block = btrp::gt(blocks, i);
int bg = block.fi.fi;
int sz = block.fi.se;
int last_change = block.se;
S.push_back(mp(mp(bg, bg + sz - 1), t - last_change));
btrp::rem(blocks, bg);
if (i > bg)
btrp::add(blocks, bg, i - bg, t);
if (i < bg + sz - 1)
btrp::add(blocks, i + 1, (bg + sz - 1) - (i + 1) + 1, t);
}
a0[i] ^= 1;
}
debug(t);
out_blocks();
}
// for (auto e : S)
// debug(e.fi.fi, e.fi.se, e.se);
//
int fnw[n + 1];
memset(fnw, 0, sizeof(fnw));
auto fadd = [&](int i, int d)
{
for (i = n - i; i <= n; i += i & -i)
fnw[i] += d;
};
auto fgt = [&](int i)
{
int ans = 0;
for (i = n - i; i >= 1; i -= i & -i)
ans += fnw[i];
return ans;
};
vector< pair<pii, pii> > Z;
for (int t = 1; t <= q; ++t)
{
auto &q = que[t];
if (q.se != -1)
{
int l = q.fi;
int r = q.se;
Z.push_back(mp(mp(l, r), mp(t, -1)));
}
}
sort(all(S));
sort(all(Z));
int ptr1 = 0, ptr2 = 0;
for (int l = 0; l < n; ++l)
{
while (ptr1 < S.size() && S[ptr1].fi.fi == l)
{
int R = S[ptr1].fi.se;
int D = S[ptr1].se;
ptr1++;
fadd(R, D);
}
while (ptr2 < Z.size() && Z[ptr2].fi.fi == l)
{
int R = Z[ptr2].fi.se;
Z[ptr2].se.se = fgt(R);
auto block = btrp::gt(blocks, l);
int bg = block.fi.fi;
int sz = block.fi.se;
int last_change = block.se;
if (bg != INF32 && R <= bg + sz - 1)
{
Z[ptr2].se.se += Z[ptr2].se.fi - last_change;
}
ptr2++;
}
}
sort(all(Z), [&](pair<pii, pii> p1, pair<pii, pii> p2) -> bool
{
return p1.se.fi < p2.se.fi;
});
for (auto e : Z)
cout << e.se.se << '\n';
exit(0);
}
return 0;
}
Compilation message
street_lamps.cpp: In constructor 'btrp::Node::Node(int, int, int)':
street_lamps.cpp:49:21: warning: 'btrp::Node::last_change' will be initialized after [-Wreorder]
int bg, sz, last_change;
^~~~~~~~~~~
street_lamps.cpp:48:13: warning: 'int btrp::Node::y' [-Wreorder]
int y;
^
street_lamps.cpp:53:9: warning: when initialized here [-Wreorder]
Node(int _bg, int _sz, int _last_change): bg(_bg), sz(_sz), last_change(_last_change), y(rng()), l(0), r(0) {}
^~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:318:54: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (cur_bg != -1 && (i == n || i > 0 && a0[i - 1] == 1))
~~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In lambda function:
street_lamps.cpp:334:43: warning: statement has no effect [-Wunused-value]
debug(bg, sz, last_change);
^
street_lamps.cpp:331:21: warning: unused variable 'bg' [-Wunused-variable]
int bg = block.fi.fi;
^~
street_lamps.cpp:332:21: warning: unused variable 'sz' [-Wunused-variable]
int sz = block.fi.se;
^~
street_lamps.cpp:333:21: warning: unused variable 'last_change' [-Wunused-variable]
int last_change = block.se;
^~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:407:21: warning: statement has no effect [-Wunused-value]
debug(t);
^
street_lamps.cpp:446:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr1 < S.size() && S[ptr1].fi.fi == l)
~~~~~^~~~~~~~~~
street_lamps.cpp:453:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (ptr2 < Z.size() && Z[ptr2].fi.fi == l)
~~~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
97 ms |
4192 KB |
Output is correct |
| 2 |
Correct |
102 ms |
4216 KB |
Output is correct |
| 3 |
Correct |
95 ms |
4396 KB |
Output is correct |
| 4 |
Correct |
119 ms |
8264 KB |
Output is correct |
| 5 |
Correct |
136 ms |
8460 KB |
Output is correct |
| 6 |
Correct |
122 ms |
8200 KB |
Output is correct |
| 7 |
Correct |
124 ms |
8080 KB |
Output is correct |
| 8 |
Correct |
139 ms |
9484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
4480 KB |
Output is correct |
| 2 |
Correct |
8 ms |
4480 KB |
Output is correct |
| 3 |
Correct |
8 ms |
4480 KB |
Output is correct |
| 4 |
Correct |
8 ms |
4480 KB |
Output is correct |
| 5 |
Correct |
94 ms |
10376 KB |
Output is correct |
| 6 |
Correct |
138 ms |
10676 KB |
Output is correct |
| 7 |
Correct |
165 ms |
10764 KB |
Output is correct |
| 8 |
Correct |
186 ms |
12812 KB |
Output is correct |
| 9 |
Correct |
91 ms |
7804 KB |
Output is correct |
| 10 |
Correct |
95 ms |
8056 KB |
Output is correct |
| 11 |
Correct |
100 ms |
8056 KB |
Output is correct |
| 12 |
Correct |
192 ms |
11380 KB |
Output is correct |
| 13 |
Correct |
190 ms |
12808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
384 KB |
Output is correct |
| 2 |
Correct |
10 ms |
512 KB |
Output is correct |
| 3 |
Correct |
10 ms |
512 KB |
Output is correct |
| 4 |
Correct |
10 ms |
512 KB |
Output is correct |
| 5 |
Execution timed out |
5099 ms |
11456 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
