Submission #634644

#	Time	Username	Problem	Language	Result	Execution time	Memory
634644		dutinmeow	Street Lamps (APIO19_street_lamps)	C++17	60 / 100	5074 ms	243892 KiB

street_lamps

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>

template<class Base>
class segment_tree : public Base {
    using T = typename Base::T;
    using Base::dval;
    using Base::merge;
    using Base::apply;
 
protected:
    size_t n;
 
    struct node {
        T v;
        int l, r;
        node() = default;
        node(T _v, int _l, int _r) : v(_v), l(_l), r(_r) {}
    };
 
    int root;
    std::vector<node> tree;
 
    size_t new_node() {
        tree.emplace_back(dval, -1, -1);
        return tree.size() - 1;
    }
 
private:
    void update(int i, T v, int t, int tl, int tr) {
        if (tl == tr) {
            apply(tree[t].v, v);
            return;
        }
 
        int tm = (tl + tr) / 2;
 
        if (i <= tm) {
            if (tree[t].l == -1)
                tree[t].l = new_node();
 
            update(i, v, tree[t].l, tl, tm);
        } else {
            if (tree[t].r == -1)
                tree[t].r = new_node();
 
            update(i, v, tree[t].r, tm + 1, tr);
        }
 
        tree[t].v = merge(tree[t].l == -1 ? dval : tree[tree[t].l].v, tree[t].r == -1 ? dval : tree[tree[t].r].v);
    }
 
    T query(int l, int r, int t, int tl, int tr) {
        if (r < tl || tr < l)
            return dval;
 
        if (l <= tl && tr <= r)
            return tree[t].v;
 
        int tm = (tl + tr) / 2;
        return merge(tree[t].l == -1 ? dval : query(l, r, tree[t].l, tl, tm), tree[t].r == -1 ? dval : query(l, r,
                     tree[t].r, tm + 1, tr));
    }
 
public:
    segment_tree() = default;
 
    segment_tree(size_t _n) {
        init(_n);
    }
 
    void init(size_t _n) {
        n = _n;
        root = new_node();
    }
 
    void reserve(size_t _n) {
        tree.reserve(_n);
    }
 
    void clear() {
        tree.clear();
    }
 
    void update(int i, T v) {
        update(i, v, root, 0, n - 1);
    }
 
    T query(int l, int r) {
        return query(l, r, root, 0, n - 1);
    }
};
 
struct segment_tree_template {
    using T = int;
    const T dval = 0;
    T merge(T a, T b) { return a + b; }
    void apply(T &a, T b) { a += b; }
};
 
class Fentree {
    size_t n;
    std::vector<segment_tree<segment_tree_template>> tree;
 
public:
    Fentree() = default;
 
    Fentree(size_t _n) {
        init(_n);
    }
 
    void init(size_t _n) {
        n = _n;
        tree.resize(n + 1);
        for (int i = 1; i <= n; i++)
            tree[i].init(n);
    }
 
    void update(int i, int j, int v) {
        for (i++; i <= n; i += i & -i)
            tree[i].update(j, v);
    }
 
    int query(int i, int l, int r) {
        int ret = 0;
        for (i++; i; i -= i & -i)
            ret += tree[i].query(l, r);
        return ret;
    }
 
    int query(int i, int j, int l, int r) {
        return query(j, l, r) - query(i - 1, l, r);
    }
};
 
int main() {
	using namespace std;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

    int N, Q;
    string S;
    cin >> N >> Q >> S;
    set<int> off;
    Fentree bit(N + 1);
 
    for (int i = 0; i < N; i++) {
        if (S[i] == '0') {
            auto [it, b] = off.insert(i);
            int r = *it - 1;
            int l = (it == off.begin() ? 0 : *prev(it) + 1);
            // update [l, r] x [l, r]
            bit.update(l, l, Q);
            bit.update(r + 1, l, -Q);
            bit.update(l, r + 1, -Q);
            bit.update(r + 1, r + 1, Q);
        } else if (i == N - 1) {
            int r = N - 1;
            int l = (off.empty() ? 0 : *prev(off.end()) + 1);
            // update [l, r] x [l, r]
            bit.update(l, l, Q);
            bit.update(r + 1, l, -Q);
            bit.update(l, r + 1, -Q);
            bit.update(r + 1, r + 1, Q);
        }
    }
 
    for (int q = 1; q <= Q; q++) {
        string t;
        cin >> t;
 
        if (t == "query") {
            int l, r;
            cin >> l >> r;
            l--, r -= 2;
 
            if (off.lower_bound(l) == off.upper_bound(r)) {
                cout << bit.query(0, l, 0, r) - (Q - q) << '\n';
            } else {
                cout << bit.query(0, l, 0, r) << '\n';
            }
        } else if (t == "toggle") {
            int k;
            cin >> k;
            k--;
 
            if (S[k] == '0') {
                S[k] = '1';
                off.erase(k);
                auto itl = off.lower_bound(k);
                int l = (itl == off.begin() ? 0 : *prev(itl) + 1);
                auto itr = off.upper_bound(k);
                int r = (itr == off.end() ? N - 1 : *itr - 1);
                // update [l, k] x [k, r]
                bit.update(l, k, Q - q);
                bit.update(l, r + 1, q - Q);
                bit.update(k + 1, k, q - Q);
                bit.update(k + 1, r + 1, Q - q);
            } else {
                S[k] = '0';
                auto itl = off.lower_bound(k);
                int l = (itl == off.begin() ? 0 : *prev(itl) + 1);
                auto itr = off.upper_bound(k);
                int r = (itr == off.end() ? N - 1 : *itr - 1);
                off.insert(k);
                // update [l, k] x [k, r]
                bit.update(l, k, q - Q);
                bit.update(l, r + 1, Q - q);
                bit.update(k + 1, k, Q - q);
                bit.update(k + 1, r + 1, q - Q);
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void Fentree::init(size_t)':
street_lamps.cpp:117:27: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  117 |         for (int i = 1; i <= n; i++)
      |                         ~~^~~~
street_lamps.cpp: In member function 'void Fentree::update(int, int, int)':
street_lamps.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'size_t' {aka 'long unsigned int'} [-Wsign-compare]
  122 |         for (i++; i <= n; i += i & -i)
      |                   ~~^~~~

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