/*
The idea is that you maintain a 2D Fenwick Tree with the begin coordinate of a
segment in the first dimension and the end coordinate of a segment in the second
dimension. When a lamp is toggled on, find the nearest lamps to the left and
right not turned on and increment all segments in the Fenwick Tree that now cannot
be used anymore with the current time. When the lamp is toggled off, decrement.
Finding the next / previous lamp thats off using a std::set was too slow, so I used
a segment tree.
As a last optimization, remember that Binary Search is a very general technique.
I allocated the 2D Fenwick Tree statically and submitted ~10 times to binary
search a good size for the static array such that it doesn't segfault.
*/
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#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
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
from /usr/include/c++/10/ext/atomicity.h:35,
from /usr/include/c++/10/bits/ios_base.h:39,
from /usr/include/c++/10/ios:42,
from /usr/include/c++/10/istream:38,
from /usr/include/c++/10/sstream:38,
from /usr/include/c++/10/complex:45,
from /usr/include/c++/10/ccomplex:39,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
from street_lamps.cpp:17:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
102 | __gthrw(pthread_once)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
103 | __gthrw(pthread_getspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
104 | __gthrw(pthread_setspecific)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
106 | __gthrw(pthread_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
107 | __gthrw(pthread_join)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
108 | __gthrw(pthread_equal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
109 | __gthrw(pthread_self)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
110 | __gthrw(pthread_detach)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
112 | __gthrw(pthread_cancel)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
114 | __gthrw(sched_yield)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
116 | __gthrw(pthread_mutex_lock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
117 | __gthrw(pthread_mutex_trylock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
119 | __gthrw(pthread_mutex_timedlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
121 | __gthrw(pthread_mutex_unlock)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
122 | __gthrw(pthread_mutex_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
123 | __gthrw(pthread_mutex_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
125 | __gthrw(pthread_cond_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
126 | __gthrw(pthread_cond_broadcast)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
127 | __gthrw(pthread_cond_signal)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
128 | __gthrw(pthread_cond_wait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
129 | __gthrw(pthread_cond_timedwait)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
130 | __gthrw(pthread_cond_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
132 | __gthrw(pthread_key_create)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
133 | __gthrw(pthread_key_delete)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
134 | __gthrw(pthread_mutexattr_init)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
135 | __gthrw(pthread_mutexattr_settype)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
136 | __gthrw(pthread_mutexattr_destroy)
| ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
237 | __gthrw2(__gthrw_(__pthread_key_create),
| ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
73 | _GLIBCXX_GTHRW(rwlock_rdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:73:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
74 | _GLIBCXX_GTHRW(rwlock_tryrdlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:74:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
75 | _GLIBCXX_GTHRW(rwlock_wrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:75:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
76 | _GLIBCXX_GTHRW(rwlock_trywrlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:76:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
77 | _GLIBCXX_GTHRW(rwlock_unlock)
| ^~~~~~~~~~~~~~
/usr/include/c++/10/shared_mutex:77:3: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
91 | __gthrw(pthread_rwlock_timedrdlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:91:4: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
101 | __gthrw(pthread_rwlock_timedwrlock);
| ^~~~~~~
/usr/include/c++/10/shared_mutex:101:4: error: attribute value 'tune=native' was already specified in 'target' attribute
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:194:23: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
194 | 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:85: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:175:88: required from here
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)
| ~~^~~~
street_lamps.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
61 | while (i <= N)
| ~~^~~~
