Submission #684810

#	Time	Username	Problem	Language	Result	Execution time	Memory
684810		KiriLL1ca	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1450 ms	324200 KiB

street_lamps

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())
#define pb push_back
#define fr first
#define sc second
#define pw(x) (1ll << x)

using namespace std;

typedef long long ll;
typedef pair <ll, ll> pll;

template <typename T> inline bool umax (T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool umin (T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }

struct do_2d {
    struct fen {
        vector <int> t, cp;
        inline void make () { sort(all(cp)); cp.erase(unique(all(cp)), cp.end()); t.resize(sz(cp) + 100); }
        inline void _upd (int p, int x) { for (p += 5; p < sz(t); p += (p & -p)) t[p] += x; }
        inline int _get (int p) { int res = 0; for (p += 5; p; p -= (p & -p)) res += t[p]; return res; }
        inline void upd (int p, int x) {
            p = lower_bound(all(cp), p) - cp.begin();
            _upd(0, x); _upd(p + 1, -x);
        }
        inline int get (int r) {
            r = lower_bound(all(cp), r) - cp.begin();
            return _get(r);
        }
        inline int get (int l, int r) { return get(r) - get(l - 1); }
    };

    int n;
    vector <fen> t;
    do_2d (int n = 0) : n(n), t(4 * n) {}

    inline void add (int v, int tl, int tr, int l, int r, int x) {
        if (tl > r || l > tr) return;
        if (l <= tl && tr <= r) return void(t[v].cp.pb(x));
        int tm = (tl + tr) >> 1;
        add(v << 1, tl, tm, l, r, x); add(v << 1 | 1, tm + 1, tr, l, r, x);
    }
    inline void build (int v, int tl, int tr) {
        t[v].make();
        if (tl == tr) return;
        int tm = (tl + tr) >> 1;
        build(v << 1, tl, tm); build(v << 1 | 1, tm + 1, tr);
    }

    inline void upd (int v, int tl, int tr, int l, int r, int x, int y) {
        if (l > tr || tl > r) return;
        if (l <= tl && tr <= r) return void(t[v].upd(x, y));
        int tm = (tl + tr) >> 1;
        upd(v << 1, tl, tm, l, r, x, y);
        upd(v << 1 | 1, tm + 1, tr, l, r, x, y);
    }

    inline int get (int v, int tl, int tr, int x, int y) {
        int res = t[v].get(y);
        if (tl == tr) return res;
        int tm = (tl + tr) >> 1;
        if (x <= tm) return res + get(v << 1, tl, tm, x, y);
        else return res + get(v << 1 | 1, tm + 1, tr, x, y);
    }

    inline void add (int l, int r, int x) { add(1, 0, n - 1, l, r, x); }
    inline void build () { build(1, 0, n - 1); }
    inline void upd (int l, int r, int x, int y) { upd(1, 0, n - 1, l, r, x, y); }
    inline int get (int x, int y) { return get(1, 0, n - 1, x, y); }
};

inline void solve () {
    int n, q; cin >> n >> q;
    string s; cin >> s;
    vector <array <int, 3>> req (q);
    for (int i = 0; i < q; ++i) {
        string t; cin >> t;
        if (t == "toggle") {
            int id; cin >> id; --id;
            req[i] = {0, id, -1};
        }
        else {
            int l, r; cin >> l >> r; --l, --r;
            req[i] = {1, l, r};
        }
    }

    set <array <int, 3>> seg;
    vector <int> lamp (n);
    for (int i = 0; i < n; ++i) lamp[i] = s[i] - '0';

    for (int i = 0, j; i < n; ) {
        j = i;
        while (j < n && lamp[i] == lamp[j]) ++j;
        if (lamp[i]) seg.insert({i, j, 0});
        i = j;
    }

    const int inf = 1e9 + 7;

    function <set <array <int, 3>>::iterator(int x)> get_iter = [&] (int x) {
        auto it = seg.upper_bound({x, inf, inf});
        if (it != seg.begin()) --it;
        if (it == seg.end()) return seg.end();
        auto [l, r, _] = *it;
        if (l <= x && x <= r) return it;
        else return seg.end();
    };

    do_2d st (n + 1);
    for (auto [l, r, time] : seg) st.add(l, r, r);

    int time = 1;
    for (auto [tp, i, _] : req) {
        if (tp) continue;
        if (lamp[i]) {
            lamp[i] = 0;
            auto it = get_iter(i);
            auto [l, r, t] = *it; seg.erase(it);
            if (l < i) {
                seg.insert({l, i, time});
                st.add(l, i, i);
            }
            if (i + 1 < r) {
                seg.insert({i + 1, r, time});
                st.add(i + 1, r, r);
            }
        }
        else {
            lamp[i] = 1;
            int l = i, r = i + 1;
            auto it = get_iter(r);
            if (it != seg.end()) {
                r = (*it)[1];
                seg.erase(it);
            }
            it = get_iter(l);
            if (it != seg.end()) {
                l = (*it)[0];
                seg.erase(it);
            }

            seg.insert({l, r, time});
            st.add(l, r, r);
        }
        ++time;
    }
    st.build();

    seg.clear();
    for (int i = 0; i < n; ++i) lamp[i] = s[i] - '0';

    for (int i = 0, j; i < n; ) {
        j = i;
        while (j < n && lamp[i] == lamp[j]) ++j;
        if (lamp[i]) seg.insert({i, j, 0});
        i = j;
    }

    time = 1;
    for (auto [tp, l, r] : req) {
        if (tp) {
            int res = st.get(l, r);
            auto it = get_iter(l);
            if (it != seg.end() && (*it)[1] >= r) {
                res += time - (*it)[2];
            }
            cout << res << endl;
        }
        else {
            int i = l;
            if (lamp[i]) {
                lamp[i] = 0;
                auto it = get_iter(i);
                auto [l, r, t] = *it; seg.erase(it);
                st.upd(l, r, r, time - t);
                if (l < i) {
                    seg.insert({l, i, time});
                }
                if (i + 1 < r) {
                    seg.insert({i + 1, r, time});
                }
            }
            else {
                lamp[i] = 1;
                int l = i, r = i + 1;
                auto it = get_iter(r);
                if (it != seg.end()) {
                    r = (*it)[1];
                    st.upd(i + 1, r, r, time - (*it)[2]);
                    seg.erase(it);
                }
                it = get_iter(l);
                if (it != seg.end()) {
                    l = (*it)[0];
                    st.upd(l, i, i, time - (*it)[2]);
                    seg.erase(it);
                }
                seg.insert({l, r, time});
            }
        }
        ++time;
    }
}

int main ()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif // LOCAL
    int t = 1; // cin >> t;
    while (t--) solve();
    return 0;
}

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