Submission #343500

#	Time	Username	Problem	Language	Result	Execution time	Memory
343500		12tqian	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1493 ms	57340 KiB

street_lamps

#include <bits/stdc++.h>

template<class T> struct Offline2DBIT { 
    bool mode = 0; // mode = 1 -> initialized
    int sz;
    std::vector<std::pair<int, int>> todo;
    std::vector<int> cnt, st, val;
    std::vector<T> bit;
    void init(int sz_) {
        sz = sz_;
        sz++;
        cnt.assign(sz, 0);
        st.assign(sz, 0);
        assert(!mode); mode = 1;
        std::vector<int> lst(sz, 0);
        cnt.assign(sz, 0);
        sort(todo.begin(), todo.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) { 
            return a.second < b.second; });
        for (auto& t : todo) 
            for (int x = t.first; x < sz; x += x & -x)
                if (lst[x] != t.second)
                    lst[x] = t.second, cnt[x]++;
        int sum = 0; 
        for (int i = 0; i < sz; i++)
            lst[i] = 0, st[i] = (sum += cnt[i]);
        val.resize(sum); bit.resize(sum);
        reverse(todo.begin(), todo.end());
        for (auto& t : todo) 
            for (int x = t.first; x < sz; x += x & -x)
                if (lst[x] != t.second)
                    lst[x] = t.second, val[--st[x]] = t.second;
    }
    int rank(int y, int l, int r) {
        return std::upper_bound(val.begin() + l, val.begin() + r, y) - val.begin() - l;
    }
    void inner_update(int x, int y, T t) {
        for (y = rank(y, st[x], st[x] + cnt[x]); y <= cnt[x]; y += y & -y)
            bit[st[x] + y - 1] += t;
    }
    void update(int x, int y, T t) {
        x++, y++;
        if (!mode) todo.push_back({x, y});
        else 
            for (; x < sz; x += x & -x)
                inner_update(x, y, t);
    }
    int inner_query(int x, int y) {
        T res = 0;
        for (y = rank(y, st[x], st[x] + cnt[x]); y; y -= y & -y)
            res += bit[st[x] + y - 1];
        return res;
    }
    T query(int x, int y) {
        x++, y++;
        assert(mode);
        T res = 0;
        for (; x; x -= x & -x) 
            res += inner_query(x, y);
        return res;
    }
    T query(int xl, int xr, int yl, int yr) {
        return query(xr, yr) - query(xl - 1, yr) - query(xr, yl - 1) + query(xl - 1, yl - 1);
    }
};

int main() { 
    using namespace std;
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    string s; cin >> s;
    set<pair<int, int>> ranges;
    int i1 = 0;
    int i2 = 0;
    while (i1 != n) {
        while (i2 != n - 1 && s[i2 + 1] == s[i1]) ++i2;
        if (s[i1] == '1') {
            ranges.emplace(i1, i2);
        }
        i1 = ++i2;
    }
    Offline2DBIT<long long> O;
    vector<vector<array<int, 3>>> changes(q + 1);
    vector<pair<int, int>> queries;
    queries.push_back({-1, -1});
    vector<int> add(q + 1);
    for (int i = 1; i <= q; i++) {
        string t; cin >> t;
        if (t == "toggle") {
            int id; cin >> id;
            id--;
            queries.emplace_back(id, -1);
            auto it = ranges.lower_bound({id + 1, -1});
            bool contained = false;
            if (it != ranges.begin()) {
                it = prev(it);
                if (it->first <= id && id <= it->second) {
                    changes[i].push_back({it->first, it->second, i});
                    O.update(it->first, it->second, i);
                    int l1 = it->first;
                    int r1 = id - 1;
                    int l2 = id + 1;
                    int r2 = it->second;
                    if (l1 <= r1) {
                        changes[i].push_back({l1, r1, -i});
                        O.update(l1, r1, -i);
                        ranges.emplace(l1, r1);
                    }
                    if (l2 <= r2) {
                        changes[i].push_back({l2, r2, -i});
                        O.update(l2, r2, -i);
                        ranges.emplace(l2, r2);
                    }
                    ranges.erase({l1, r2});
                    contained = true;
                }
            }
            if (!contained) {
                pair<int, int> bef = {-1, -1};
                pair<int, int> aft = {-1, -1};
                pair<int, int> cur = {id, id};
                it = ranges.lower_bound({id, id});
                if (it != ranges.end() && it->first == id + 1) {
                    aft = *it;
                    changes[i].push_back({aft.first, aft.second, i});
                    O.update(aft.first, aft.second, i);
                    cur.second = aft.second;
                }
                if (it != ranges.begin() && prev(it)->second == id - 1) {
                    bef = *prev(it);
                    changes[i].push_back({bef.first, bef.second, i});
                    O.update(bef.first, bef.second, i);
                    cur.first = bef.first;
                }
                changes[i].push_back({cur.first, cur.second, -i});
                O.update(cur.first, cur.second, -i);
                ranges.emplace(cur.first, cur.second);
                if (bef.first != -1) {
                    ranges.erase(bef);
                }
                if (aft.first != -1) {
                    ranges.erase(aft);
                }
            }
        } else {
            int l, r; cin >> l >> r;
            r--;
            l--, r--;
            queries.emplace_back(l, r);
            auto it = ranges.lower_bound({l + 1, -1});
            if (it != ranges.begin()) {
                it = prev(it);
                if (it->first <= l && r <= it->second) {
                    add[i] += i;
                }
            }
        }   
    }
    O.init(n);
    for (int i = 1; i <= q; i++) {
        if (queries[i].second == -1) {
            for (auto c : changes[i]) {
                O.update(c[0], c[1], c[2]);
            }
        } else {
            int l = queries[i].first;
            int r = queries[i].second;
            long long ans = O.query(0, l, r, n - 1) + add[i];
            cout << ans << '\n';
        }
    }
    return 0;
}

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