Submission #343498

#	Time	Username	Problem	Language	Result	Execution time	Memory
343498		12tqian	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1498 ms	57312 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;

#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define eb emplace_back
#define pb push_back
#define f first
#define s second
#define mp make_pair
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef vector<ll> vl;


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_;
        cnt.assign(sz, 0);
        st.assign(sz, 0);
    }
    void build() { 
        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) {
        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) {
        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() { 
    cin.tie(0)->sync_with_stdio(0);
    int n, q; cin >> n >> q;
    string s; cin >> s;
    set<pi> 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+1, i2+1);
        }
        i1 = ++i2;
    }
    Offline2DBIT<ll> O;
    O.init(n + 5);
    vector<vector<array<int, 3>>> changes(q + 5);
    vpi queries;
    queries.pb({-1, -1});
    vi add(q + 1);
    f1r(i, 1, q + 1) {
        string t; cin >> t;
        if (t == "toggle") {
            int id; cin >> id;
            queries.eb(id, -1);
            auto it = ranges.lower_bound({id + 1, -1});
            bool contained = false;
            if (it != ranges.begin()) {
                it = prev(it);
                if (it->f <= id && id <= it->s) {
                    changes[i].pb({it->f, it->s, i});
                    O.update(it->f, it->s, i);
                    int l1 = it->f;
                    int r1 = id-1;
                    int l2 = id+1;
                    int r2 = it->s;
                    if (l1 <= r1) {
                        changes[i].pb({l1, r1, -i});
                        O.update(l1, r1, -i);
                        ranges.emplace(l1, r1);
                    }
                    if (l2 <= r2) {
                        changes[i].pb({l2, r2, -i});
                        O.update(l2, r2, -i);
                        ranges.emplace(l2, r2);
                    }
                    ranges.erase({l1, r2});
                    contained = true;
                }
            }
            if (!contained) {
                pi bef = {-1, -1};
                pi aft = {-1, -1};
                pi cur = {id, id};
                it = ranges.lower_bound({id, id});
                if (it != ranges.end() && it->f == id + 1) {
                    aft = *it;
                    changes[i].pb({aft.f, aft.s, i});
                    O.update(aft.f, aft.s, i);
                    cur.s = aft.s;
                }
                if (it != ranges.begin() && prev(it)->s == id - 1) {
                    bef = *prev(it);
                    changes[i].pb({bef.f, bef.s, i});
                    O.update(bef.f, bef.s, i);
                    cur.f = bef.f;
                }
                changes[i].pb({cur.f, cur.s, -i});
                O.update(cur.f, cur.s, -i);
                ranges.emplace(cur.f, cur.s);
                if (bef.f != -1) {
                    ranges.erase(bef);
                }
                if (aft.f != -1) {
                    ranges.erase(aft);
                }
            }
        } else {
            int l, r; cin >> l >> r;
            r--;
            queries.eb(l, r);
            auto it = ranges.lower_bound({l + 1, -1});
            if (it != ranges.begin()) {
                it = prev(it);
                if (it->f <= l && r <= it->s) {
                    add[i] += i;
                }
            }
        }   
    }
    O.build();
    f1r(i, 1, q+1) {
        if (queries[i].s == -1) {
            for (auto c : changes[i]) {
                O.update(c[0], c[1], c[2]);
            }
        } else {
            int l = queries[i].f;
            int r = queries[i].s;
            ll ans = O.query(1, l, r, n) + 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