| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1326561 | ee23b179_cp | Street Lamps (APIO19_street_lamps) | C++20 | 0 ms | 0 KiB |
/*
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 (at least
on DMOJ), so I used a segment tree.
On DMOJ, this was still too slow.
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 SegmentTree
{
bitset<2 * 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;
SegmentTree<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';
}
}
}