Submission #374458

#	Time	Username	Problem	Language	Result	Execution time	Memory
374458		KoD	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	2245 ms	117596 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(2 * n);
        fen.resize(2 * n);
        for (int i = 0; i < (int) x.size(); ++i) {
            pts[x[i] + n].push_back(y[i]);
        }
        for (int i = n; i < 2 * n; ++i) {
            std::sort(pts[i].begin(), pts[i].end());
        }
        for (int i = n - 1; i > 0; --i) {
            pts[i].reserve(pts[i * 2].size() + pts[i * 2 + 1].size());
            std::copy(pts[i * 2].begin(), pts[i * 2].end(), std::back_inserter(pts[i]));
            std::copy(pts[i * 2 + 1].begin(), pts[i * 2 + 1].end(), std::back_inserter(pts[i]));
            std::inplace_merge(pts[i].begin(), pts[i].begin() + pts[i * 2].size(), pts[i].end());
        }
        for (int i = 1; i < 2 * n; ++i) {
            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 += size(), r += size(); l < r; l >>= 1, r >>= 1) {
            if (l & 1) {
                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);
                l += 1;
            }
            if (r & 1) {
                r -= 1;
                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 += size(); x > 0; x >>= 1) {
            ret += fen[x].get(std::lower_bound(pts[x].begin(), pts[x].end(), y) - pts[x].begin());
        }
        return ret;
    }
    int size() const {
        return (int) pts.size() / 2;
    }
};  

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