#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2")
#include <bits/stdc++.h>
using namespace std;
template <typename T, size_t N, size_t M>
struct FenwickTree
{
unsigned a[N + 1], d[M];
vector<unsigned> c[N];
T t[M];
bool active = 0;
void initialize()
{
size_t m = 0;
active = 1;
for (size_t i = 0; i < N; i++)
{
a[i] = m;
sort(c[i].begin(), c[i].end());
c[i].resize(unique(c[i].begin(), c[i].end()) - c[i].begin());
copy(c[i].begin(), c[i].end(), d + a[i]);
m += c[i].size();
}
a[N] = m;
}
void increment(int64_t i, int64_t j, T x)
{
++i, ++j;
if (active)
{
while (i <= N)
{
int64_t k = upper_bound(d + a[i - 1], d + a[i], j) - (d + a[i - 1]);
while (k <= a[i] - a[i - 1])
{
t[a[i - 1] + k - 1] += x;
k += k & -k;
}
i += i & -i;
}
}
else
{
while (i <= N)
c[i - 1].push_back(j), i += i & -i;
}
}
T pointQuery(int64_t i, int64_t j) // it's really prefix sum
{
++i, ++j;
T x = 0;
while (i)
{
int64_t k = upper_bound(d + a[i - 1], d + a[i], j) - (d + a[i - 1]);
while (k)
{
x += t[a[i - 1] + k - 1];
k -= k & -k;
}
i -= i & -i;
}
return x;
}
void rangeIncrement(int64_t i, int64_t j, int64_t k, int64_t l, T x)
{
increment(i, j, x);
increment(k + 1, j, -x);
increment(i, l + 1, -x);
increment(k + 1, l + 1, x);
}
};
template <size_t N>
struct OrSegmentTree
{
bitset<1 << (32 - __builtin_clz(N))> t;
bool operator[](size_t i) { return t[N + i]; }
void reset() { t.reset(); }
void set(size_t i, bool x)
{
t[i += N] = x;
while (i >>= 1)
t[i] = t[2 * i] | t[2 * i + 1];
}
ptrdiff_t previousNonzero(size_t i)
{
i += N;
do
{
if ((i & 1) && t[i - 1])
{
--i;
while (i < N)
i = 2 * i + t[2 * i + 1];
return i - N;
}
} while ((i >>= 1) > 1);
return -1;
}
ptrdiff_t nextNonzero(size_t i)
{
i += N;
do
{
if (!(i & 1) && t[i + 1])
{
++i;
while (i < N)
i = 2 * i + !t[2 * i];
return i - N;
}
} while ((i >>= 1) > 1);
return N;
}
};
constexpr size_t N = 300002;
FenwickTree<int, N, 3725000> tree;
OrSegmentTree<1 << 19> tree2; // set is too slow
int queries[N][2];
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
size_t n, q;
string s;
cin >> n >> q >> s;
for (size_t i = 0; i < n; i++)
if (s[i] == '0')
tree2.set(i, 1);
for (size_t i = 0; i < q; i++)
{
string r;
cin >> r;
if (r == "query")
{
cin >> queries[i][0] >> queries[i][1];
--queries[i][0], --queries[i][1];
}
else
{
cin >> queries[i][1], --queries[i][1];
queries[i][0] = -1;
if (!tree2[queries[i][1]])
{
tree.rangeIncrement(tree2.previousNonzero(queries[i][1]) + 1,
queries[i][1] + 1, queries[i][1],
min<size_t>(tree2.nextNonzero(queries[i][1]), n), 0);
tree2.set(queries[i][1], 1);
}
else
{
tree2.set(queries[i][1], 0);
tree.rangeIncrement(tree2.previousNonzero(queries[i][1]) + 1,
queries[i][1] + 1, queries[i][1],
min<size_t>(tree2.nextNonzero(queries[i][1]), n), 0);
}
}
}
tree2.reset();
for (size_t i = 0; i < n; i++)
if (s[i] == '0')
tree2.set(i, 1);
tree.initialize();
for (int i = 0; i < q; i++)
{
if (queries[i][0] == -1)
{
if (!tree2[queries[i][1]])
{
tree.rangeIncrement(tree2.previousNonzero(queries[i][1]) + 1,
queries[i][1] + 1, queries[i][1],
min<size_t>(tree2.nextNonzero(queries[i][1]), n), i + 1);
tree2.set(queries[i][1], 1);
}
else
{
tree2.set(queries[i][1], 0);
tree.rangeIncrement(tree2.previousNonzero(queries[i][1]) + 1,
queries[i][1] + 1, queries[i][1],
min<size_t>(tree2.nextNonzero(queries[i][1]), n), -(i + 1));
}
}
else
{
bool somethingInRange = tree2.nextNonzero(queries[i][0]) < queries[i][1] ||
tree2.previousNonzero(queries[i][1]) >= queries[i][0];
cout << tree.pointQuery(queries[i][0], queries[i][1]) +
(somethingInRange ? 0 : (i + 1))
<< '\n';
}
}
}
Compilation message
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:181:23: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
181 | for (int i = 0; i < q; i++)
| ~~^~~
street_lamps.cpp: In instantiation of 'void FenwickTree<T, N, M>::increment(int64_t, int64_t, T) [with T = int; long unsigned int N = 300002; long unsigned int M = 3725000; int64_t = long int]':
street_lamps.cpp:72:9: required from 'void FenwickTree<T, N, M>::rangeIncrement(int64_t, int64_t, int64_t, int64_t, T) [with T = int; long unsigned int N = 300002; long unsigned int M = 3725000; int64_t = long int]'
street_lamps.cpp:162:88: required from here
street_lamps.cpp:35:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
35 | while (i <= N)
| ~~^~~~
street_lamps.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
48 | while (i <= N)
| ~~^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8676 KB |
Output is correct |
2 |
Correct |
10 ms |
8660 KB |
Output is correct |
3 |
Correct |
9 ms |
8680 KB |
Output is correct |
4 |
Correct |
10 ms |
8788 KB |
Output is correct |
5 |
Correct |
11 ms |
8660 KB |
Output is correct |
6 |
Correct |
8 ms |
8660 KB |
Output is correct |
7 |
Correct |
8 ms |
8664 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1121 ms |
52040 KB |
Output is correct |
2 |
Correct |
1127 ms |
50028 KB |
Output is correct |
3 |
Correct |
1155 ms |
47416 KB |
Output is correct |
4 |
Correct |
1235 ms |
62144 KB |
Output is correct |
5 |
Correct |
1099 ms |
51556 KB |
Output is correct |
6 |
Correct |
1402 ms |
70900 KB |
Output is correct |
7 |
Correct |
146 ms |
13036 KB |
Output is correct |
8 |
Correct |
168 ms |
14448 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
13 ms |
9044 KB |
Output is correct |
2 |
Correct |
12 ms |
8928 KB |
Output is correct |
3 |
Correct |
10 ms |
8788 KB |
Output is correct |
4 |
Correct |
8 ms |
8660 KB |
Output is correct |
5 |
Correct |
2358 ms |
98496 KB |
Output is correct |
6 |
Correct |
1777 ms |
78376 KB |
Output is correct |
7 |
Correct |
1113 ms |
50536 KB |
Output is correct |
8 |
Correct |
177 ms |
14176 KB |
Output is correct |
9 |
Correct |
100 ms |
12028 KB |
Output is correct |
10 |
Correct |
109 ms |
12728 KB |
Output is correct |
11 |
Correct |
96 ms |
12748 KB |
Output is correct |
12 |
Correct |
141 ms |
13064 KB |
Output is correct |
13 |
Correct |
173 ms |
14364 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
8660 KB |
Output is correct |
2 |
Correct |
11 ms |
8804 KB |
Output is correct |
3 |
Correct |
12 ms |
9024 KB |
Output is correct |
4 |
Correct |
16 ms |
9076 KB |
Output is correct |
5 |
Correct |
192 ms |
13900 KB |
Output is correct |
6 |
Correct |
771 ms |
44780 KB |
Output is correct |
7 |
Correct |
1429 ms |
69736 KB |
Output is correct |
8 |
Correct |
2177 ms |
94232 KB |
Output is correct |
9 |
Correct |
1586 ms |
70492 KB |
Output is correct |
10 |
Correct |
2054 ms |
89200 KB |
Output is correct |
11 |
Correct |
1571 ms |
70884 KB |
Output is correct |
12 |
Correct |
2008 ms |
89640 KB |
Output is correct |
13 |
Correct |
1550 ms |
70616 KB |
Output is correct |
14 |
Correct |
1985 ms |
89400 KB |
Output is correct |
15 |
Correct |
148 ms |
13064 KB |
Output is correct |
16 |
Correct |
173 ms |
14500 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
8676 KB |
Output is correct |
2 |
Correct |
10 ms |
8660 KB |
Output is correct |
3 |
Correct |
9 ms |
8680 KB |
Output is correct |
4 |
Correct |
10 ms |
8788 KB |
Output is correct |
5 |
Correct |
11 ms |
8660 KB |
Output is correct |
6 |
Correct |
8 ms |
8660 KB |
Output is correct |
7 |
Correct |
8 ms |
8664 KB |
Output is correct |
8 |
Correct |
1121 ms |
52040 KB |
Output is correct |
9 |
Correct |
1127 ms |
50028 KB |
Output is correct |
10 |
Correct |
1155 ms |
47416 KB |
Output is correct |
11 |
Correct |
1235 ms |
62144 KB |
Output is correct |
12 |
Correct |
1099 ms |
51556 KB |
Output is correct |
13 |
Correct |
1402 ms |
70900 KB |
Output is correct |
14 |
Correct |
146 ms |
13036 KB |
Output is correct |
15 |
Correct |
168 ms |
14448 KB |
Output is correct |
16 |
Correct |
13 ms |
9044 KB |
Output is correct |
17 |
Correct |
12 ms |
8928 KB |
Output is correct |
18 |
Correct |
10 ms |
8788 KB |
Output is correct |
19 |
Correct |
8 ms |
8660 KB |
Output is correct |
20 |
Correct |
2358 ms |
98496 KB |
Output is correct |
21 |
Correct |
1777 ms |
78376 KB |
Output is correct |
22 |
Correct |
1113 ms |
50536 KB |
Output is correct |
23 |
Correct |
177 ms |
14176 KB |
Output is correct |
24 |
Correct |
100 ms |
12028 KB |
Output is correct |
25 |
Correct |
109 ms |
12728 KB |
Output is correct |
26 |
Correct |
96 ms |
12748 KB |
Output is correct |
27 |
Correct |
141 ms |
13064 KB |
Output is correct |
28 |
Correct |
173 ms |
14364 KB |
Output is correct |
29 |
Correct |
8 ms |
8660 KB |
Output is correct |
30 |
Correct |
11 ms |
8804 KB |
Output is correct |
31 |
Correct |
12 ms |
9024 KB |
Output is correct |
32 |
Correct |
16 ms |
9076 KB |
Output is correct |
33 |
Correct |
192 ms |
13900 KB |
Output is correct |
34 |
Correct |
771 ms |
44780 KB |
Output is correct |
35 |
Correct |
1429 ms |
69736 KB |
Output is correct |
36 |
Correct |
2177 ms |
94232 KB |
Output is correct |
37 |
Correct |
1586 ms |
70492 KB |
Output is correct |
38 |
Correct |
2054 ms |
89200 KB |
Output is correct |
39 |
Correct |
1571 ms |
70884 KB |
Output is correct |
40 |
Correct |
2008 ms |
89640 KB |
Output is correct |
41 |
Correct |
1550 ms |
70616 KB |
Output is correct |
42 |
Correct |
1985 ms |
89400 KB |
Output is correct |
43 |
Correct |
148 ms |
13064 KB |
Output is correct |
44 |
Correct |
173 ms |
14500 KB |
Output is correct |
45 |
Correct |
670 ms |
40872 KB |
Output is correct |
46 |
Correct |
725 ms |
37360 KB |
Output is correct |
47 |
Correct |
879 ms |
42576 KB |
Output is correct |
48 |
Correct |
1287 ms |
61468 KB |
Output is correct |
49 |
Correct |
114 ms |
12632 KB |
Output is correct |
50 |
Correct |
135 ms |
12680 KB |
Output is correct |
51 |
Correct |
96 ms |
12908 KB |
Output is correct |
52 |
Correct |
113 ms |
12688 KB |
Output is correct |
53 |
Correct |
95 ms |
12644 KB |
Output is correct |
54 |
Correct |
98 ms |
12760 KB |
Output is correct |