Submission #722733

#	Time	Username	Problem	Language	Result	Execution time	Memory
722733		finn__	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2358 ms	98496 KiB

street_lamps

#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 (stderr)

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)
      |                    ~~^~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20