Submission #677925

#	Time	Username	Problem	Language	Result	Execution time	Memory
677925		FedShat	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2949 ms	168960 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr ll INFLL = numeric_limits<ll>::max() / 2;

template<class T>
istream &operator>>(istream &is, vector<T> &a) {
    for (auto &i : a) {
        is >> i;
    }
    return is;
}

#ifdef __APPLE__
#include "../../debug.h"
#else
#define debug(...) 42
#endif

template<typename T>
void unique(vector<T> &a) {
    sort(a.begin(), a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
}

struct Fenwick {
    vector<int> t;
    int n;

    Fenwick() {}
    Fenwick(int n) : n(n) {
        t.resize(n + 1);
    }

    void add(int i, int x) {
        for (++i; i <= n; i += i & (-i)) {
            t[i] += x;
        }
    }

    void add(int l, int r, int x) { // add on [l, r)
        add(l, x);
        add(r, -x);
    }

    int get(int i) {
        int ans = 0;
        for (; i > 0; i -= i & (-i)) {
            ans += t[i];
        }
        return ans;
    }

    int get(int l, int r) {
        return get(r) - get(l);
    }
};

struct SegTree { // merge sort tree szhatih fenwickov
    struct Node {
        Fenwick st;
        vector<int> coords;
    };

    vector<Node> tree;
    int n;

    SegTree(int n) : n(n) {
        tree.resize(4 * n);
    }

    void insert(int v, int l, int r, int i, int x) {
        tree[v].coords.push_back(x);
        if (l + 1 == r) {
            return;
        }
        int m = (l + r) / 2;
        if (i < m) {
            insert(2 * v + 1, l, m, i, x);
        } else {
            insert(2 * v + 2, m, r, i, x);
        }
    }

    void insert(int i, int x) {
        insert(0, 0, n, i, x);
    }

    void init(int v, int l, int r) {
        unique(tree[v].coords);
        tree[v].st = Fenwick(tree[v].coords.size());
        if (l + 1 == r) {
            return;
        }
        int m = (l + r) / 2;
        init(2 * v + 1, l, m);
        init(2 * v + 2, m, r);
    }

    void init() {
        init(0, 0, n);
    }

    void update(int v, int l, int r, int li, int ri, int ly, int ry, int x) {
        if (li >= r || l >= ri) {
            return;
        }
        if (li <= l && r <= ri) {
            int itl = lower_bound(tree[v].coords.begin(), tree[v].coords.end(), ly) - tree[v].coords.begin();
            int itr = lower_bound(tree[v].coords.begin(), tree[v].coords.end(), ry) - tree[v].coords.begin();
            debug(tree[v].coords, ly, ry, itl, itr);
            tree[v].st.add(itl, itr, x);
            return;
        }
        int m = (l + r) / 2;
        update(2 * v + 1, l, m, li, ri, ly, ry, x);
        update(2 * v + 2, m, r, li, ri, ly, ry, x);
    }

    void update(int lx, int rx, int ly, int ry, int x) {
        update(0, 0, n, lx, rx, ly, ry, x);
    }

    int get(int v, int l, int r, int i, int j) {
        int it = lower_bound(tree[v].coords.begin(), tree[v].coords.end(), j) - tree[v].coords.begin();
        int ans = tree[v].st.get(it + 1);
        if (l + 1 == r) {
            return ans;
        }
        int m = (l + r) / 2;
        if (i < m) {
            return ans + get(2 * v + 1, l, m, i, j);
        } else {
            return ans + get(2 * v + 2, m, r, i, j);
        }
    }

    int get(int i, int j) {
        return get(0, 0, n, i, j);
    }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#endif
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    set<int> zero;
    vector<pair<int, int>> lr, qq;
    for (int i = 0; i < q; ++i) {
        string s;
        cin >> s;
        if (s == "toggle") {
            int j;
            cin >> j;
            --j;
            qq.push_back({0, j});
        } else {
            int a, b;
            cin >> a >> b;
            a -= 1;
            b -= 2;
            lr.push_back({a, b});
            qq.push_back({1, (int) lr.size() - 1});
        }
    }
    vector<int> ans(lr.size());
    for (int i = -1; i <= n; ++i) {
        zero.insert(i);
    }
    SegTree mst(n);
    for (auto [l, r] : lr) {
        mst.insert(l, r);
    }
    mst.init();
    auto upd = [&](int pos, int t) {
        auto itr = zero.upper_bound(pos);
        auto itl = zero.lower_bound(pos);
        int r = *itr;
        int l = *prev(itl) + 1;
        // += t on [l, pos] [pos, r)
        mst.update(l, pos + 1, pos, r, t);
        // for (int i = 0; i < (int) lr.size(); ++i) {
        //     auto [li, ri] = lr[i];
        //     if (l <= li && li <= pos && pos <= ri && ri < r) {
        //         debug(li + 1, ri + 1, t);
        //         ans[i] += t;
        //     }
        // }
        if (!zero.count(pos)) {
            zero.insert(pos);
        } else {
            zero.erase(pos);
        }
    };
    Fenwick bebra(n);
    for (int i = 0; i < n; ++i) {
        if (s[i] == '1') {
            upd(i, 0);
            bebra.add(i, 1);
        }
    }
    for (int i = 1; i <= q; ++i) {
        auto [t, j] = qq[i - 1];
        if (t == 0) {
            if (s[j] == '0') {
                s[j] = '1';
                upd(j, -i);
                bebra.add(j, 1);
            } else {
                s[j] = '0';
                upd(j, i);
                bebra.add(j, -1);
            }
        } else {
            auto [l, r] = lr[j];
            int cur = mst.get(l, r);
            // debug(ans[j], cur);
            if (bebra.get(l, r + 1) != r - l + 1) {
                cout << cur << "\n";
            } else {
                cout << i + cur << "\n";
            }
        }
    }
}

Compilation message (stderr)

street_lamps.cpp: In member function 'void SegTree::update(int, int, int, int, int, int, int, int)':
street_lamps.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
street_lamps.cpp:113:13: note: in expansion of macro 'debug'
  113 |             debug(tree[v].coords, ly, ry, itl, itr);
      |             ^~~~~

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