Submission #374463

#	Time	Username	Problem	Language	Result	Execution time	Memory
374463		KoD	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1424 ms	70608 KiB

street_lamps

#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

struct Fenwick {
    Vec<int> data;
    Fenwick() = default;
    Fenwick(const int n): data(n + 1) { }
    void add(int i, const int x) {
        for (i += 1; i < (int) data.size(); i += i & -i) {
            data[i] += x;
        }   
    }
    int get(int i) const {
        int ret = 0;
        for (i += 1; i > 0; i -= i & -i) {
            ret += data[i];
        }
        return ret;
    }
};

struct Add2D {
    Vec<Vec<int>> pts;
    Vec<Fenwick> fen;
    Add2D(const Vec<int> &x, const Vec<int> &y, const int n) {
        pts.resize(n + 1);
        fen.resize(n + 1);
        for (int i = 0; i < (int) x.size(); ++i) {
            for (int k = x[i] + 1; k > 0; k -= k & -k) {
                pts[k].push_back(y[i]);
            }
        }
        for (int i = 1; i <= n; ++i) {
            std::sort(pts[i].begin(), pts[i].end());
            pts[i].erase(std::unique(pts[i].begin(), pts[i].end()), pts[i].end());
            fen[i] = Fenwick(pts[i].size());
        }
    }
    void add(int l, int r, const int d, const int u, const int v) {
        for (l += 1; l < (int) pts.size(); l += l & -l) {
            fen[l].add(std::lower_bound(pts[l].begin(), pts[l].end(), d) - pts[l].begin(), v);
            fen[l].add(std::lower_bound(pts[l].begin(), pts[l].end(), u) - pts[l].begin(), -v);
        }
        for (r += 1; r < (int) pts.size(); r += r & -r) {
            fen[r].add(std::lower_bound(pts[r].begin(), pts[r].end(), d) - pts[r].begin(), -v);
            fen[r].add(std::lower_bound(pts[r].begin(), pts[r].end(), u) - pts[r].begin(), v);
        }
    }
    int get(int x, const int y) const {
        int ret = 0;
        for (x += 1; x > 0; x -= x & -x) {
            ret += fen[x].get(std::lower_bound(pts[x].begin(), pts[x].end(), y) - pts[x].begin());
        }
        return ret;
    }
};  

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    Vec<int> state(N);
    for (auto &x: state) {
        char c;
        std::cin >> c;
        x = (c == '1');
    }
    std::set<int> off;
    for (int i = 0; i < N; ++i) {
        if (!state[i]) {
            off.insert(i);
        }
    }
    Vec<int> ans, X, Y;
    Vec<std::tuple<int, int, int, int, int>> add;
    Vec<std::pair<int, int>> qs;
    qs.reserve(Q);
    for (int t = 1; t <= Q; ++t) {
        std::string type;
        std::cin >> type;
        if (type == "query") {
            const auto idx = (int) ans.size();
            int a, b;
            std::cin >> a >> b;
            a -= 1;
            b -= 1;
            const auto itr = off.lower_bound(a);
            ans.push_back((itr == off.end() || *itr >= b) ? t : 0);
            X.push_back(a);
            Y.push_back(b);
            qs.emplace_back(idx, true);
        }
        else {
            const auto idx = (int) add.size();
            int s;
            std::cin >> s;
            s -= 1;
            if (off.find(s) == off.end()) {
                off.insert(s);
                const auto itr = off.find(s);
                const auto l = (itr == off.begin() ? 0 : *std::prev(itr) + 1);
                const auto r = (std::next(itr) == off.end() ? N : *std::next(itr));
                add.emplace_back(l, s, s + 1, r, t);
            }
            else {
                const auto itr = off.find(s);
                const auto l = (itr == off.begin() ? 0 : *std::prev(itr) + 1);
                const auto r = (std::next(itr) == off.end() ? N : *std::next(itr));
                add.emplace_back(l, s, s + 1, r, -t);
                off.erase(itr);
            }
            qs.emplace_back(idx, false);
        }
    }
    Add2D rect(X, Y, N + 1);
    for (const auto [i, f]: qs) {
        if (f) {
            ans[i] += rect.get(X[i], Y[i]);
        }
        else {
            const auto [l, r, d, u, v] = add[i];
            rect.add(l, r + 1, d, u + 1, v);
        }
    }
    for (const auto x: ans) {
        std::cout << x << '\n';
    }
    return 0;
}

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