Submission #1127759

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127759		Double_Slash	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1792 ms	125844 KiB

street_lamps

#include <bits/stdc++.h>
 
using namespace std;
using pint = pair<int, int>;

template <class T>
struct Cc : vector<T> {
    using vector<T>::begin, vector<T>::end, vector<T>::erase;

    void init() {
        sort(begin(), end());
        erase(unique(begin(), end()), end());
    }

    int inc(const T &t) { return lower_bound(begin(), end(), t) - begin(); }

    int exc(const T &t) { return upper_bound(begin(), end(), t) - begin(); }
};

struct St2 {
    int n;
    Cc<int> cc;
    vector<int> st;

    void add(int i) { cc.emplace_back(i); }

    void init() {
        cc.init();
        n = cc.size();
        st.resize(n << 1);
    }

    void update(int l, int r, int v) {
        for (l = cc.inc(l) + n, r = cc.exc(r) + n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) st[l++] += v;
            if (r & 1) st[--r] += v;
        }
    }

    int query(int i) {
        int ret = 0;
        for (i = cc.inc(i) + n; i; i >>= 1) ret += st[i];
        return ret;
    }
};

struct St {
    int n;
    vector<St2> st;

    St(int n) : n(n), st(n << 1) {}

    void add(int i, int j) { for (i += n; i; i >>= 1) st[i].add(j); }

    void init() { for (int i = n << 1; --i;) st[i].init(); }

    void update(int l, int r, int l2, int r2, int v) {
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
            if (l & 1) st[l++].update(l2, r2, v);
            if (r & 1) st[--r].update(l2, r2, v);
        }
    }

    int query(int i, int j) {
        int ret = 0;
        for (i += n; i; i >>= 1) ret += st[i].query(j);
        return ret;
    }
};

int n, q, a[300000], b[300000];
bool on[300000];
map<int, pint> ranges;

int main() {
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        char c;
        cin >> c;
        on[i] = c == '1';
        if (on[i]) {
            if (ranges.empty() or ranges.rbegin()->second.first < i - 1) ranges[i] = {i, -1};
            else ranges.rbegin()->second.first = i;
        }
    }
    St st{n};
    for (int i = 0; i < q; ++i) {
        string s;
        cin >> s >> a[i];
        a[i]--;
        if (s[0] == 't') b[i] = -1;
        else {
            cin >> b[i];
            st.add(a[i], b[i] -= 2);
        }
    }
    st.init();
    for (int i = 0; i < q; ++i) {
        auto rem = [&] (int l) {
            auto [r, t] = ranges[l];
            st.update(l, n, 0, r, i - t);
            ranges.erase(l);
        };
        if (~b[i]) {
            int ans = st.query(a[i], b[i]);
            auto it = ranges.upper_bound(a[i]);
            if (it != ranges.begin() and (--it)->second.first >= b[i]) ans += i - it->second.second;
            cout << ans << '\n';
        } else if (on[a[i]]) {
            on[a[i]] = false;
            int l = prev(ranges.upper_bound(a[i]))->first;
            int r = ranges[l].first;
            rem(l);
            if (l < a[i]) ranges[l] = {a[i] - 1, i};
            if (a[i] < r) ranges[a[i] + 1] = {r, i};
        } else {
            on[a[i]] = true;
            int l = a[i], r = a[i];
            auto it = ranges.upper_bound(r);
            if (it != ranges.end() and it->first == r + 1) {
                r = it++->second.first;
                rem(a[i] + 1);
            }
            if (it != ranges.begin() and (--it)->second.first == l - 1) rem(l = it->first);
            ranges[l] = {r, i};
        }
    }
}

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