Submission #1106101

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106101		Thunnus	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1188 ms	113484 KiB

street_lamps

/*
- Maintain a set of maximal segments of contiguous ones.
- Whenever a segment is removed, create a point (a, b, -t).
- Whenever a segment is added, create a point (a, b, +t).
- Now for each query (aq, bq, tq), count the number of points (a, b, t)
  such that a < aq , b > bq , t < tq (we don't take credit of equal elements because the given input is one-based)
- Find the total sum of t, and the number of negative and positive events.
- If one positive event is missing, add 't' into the total sum.
- This can be easily solved with CDQ divide and conquer.
- My previous idea was using a 2D sparse segment tree to do the same,
  but it uses too much memory. Alas, the remnants of my code were still there,
  so i decided to reuse the 1D version instead of creating a new code for a
  regular segment tree. 
*/
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define pii pair<int, int>
#define fi first
#define se second
#define sz(x) (int)(x).size()

const int MX = 3e5 + 5;

pii operator +(const pii &a, const pii &b){
    return {a.fi + b.fi, a.se + b.se};
}

pii operator -(const pii &a, const pii &b){
    return {a.fi - b.fi, a.se - b.se};
}

struct BIT{
    vector<pii> bit;
    BIT(int n) : bit(n + 10) {}

    inline void add(int idx, pii val){
		if(idx < 0) return;
        for(++idx; idx < sz(bit); idx += idx & -idx){
            bit[idx] = bit[idx] + val;
        }
        return;
    }

    inline pii query(int idx){
		if(idx < 0) return {0, 0};
        pii ret = {0, 0};
        for(++idx; idx; idx -= idx & -idx){
            ret = ret + bit[idx];
        }
        return ret;
    }

    inline pii query(int l, int r){
        return query(r) - query(l - 1);
    }
};

vector<array<int, 5>> updates;
vector<pii> onans, offans;
BIT on(MX), off(MX);

inline void cdq(int l, int r){
    if(l + 1 == r) return;
    int m = (l + r) / 2;
    cdq(l, m); cdq(m, r);

    vector<pair<int, pii>> offrec, onrec;
    vector<array<int, 5>> temp;
    int a = l, b = m;
    while(a < m || b < r){
        bool left;
        int cur;
        if(a >= m || (b < r && updates[b][1] <= updates[a][1])) cur = b++, left = false;
        else cur = a++, left = true;
        temp.emplace_back(updates[cur]);

        if(left && updates[cur][3] == -1){
            off.add(updates[cur][2], {updates[cur][0], 1});
            offrec.push_back({updates[cur][2], {-updates[cur][0], -1}});
        }
        else if(left && updates[cur][3] == 1){
            on.add(updates[cur][2], {updates[cur][0], 1});
            onrec.push_back({updates[cur][2], {-updates[cur][0], -1}});
        }
        else if(!left && !updates[cur][3]){
            pii onval = on.query(updates[cur][2] + 1, MX - 1), offval = off.query(updates[cur][2] + 1, MX - 1);
            onans[updates[cur][4]] = onans[updates[cur][4]] + onval, offans[updates[cur][4]] = offans[updates[cur][4]] + offval;
        }
    }

    for(int i = 0; i < sz(offrec); i++){
        off.add(offrec[i].fi, offrec[i].se);
    }
    for(int i = 0; i < sz(onrec); i++){
        on.add(onrec[i].fi, onrec[i].se);
    }
    for(int i = l; i < r; i++){
        updates[i] = temp[i - l];
    }
    temp.clear(), offrec.clear(), onrec.clear();
    return;
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, q;
    string s, type;
    cin >> n >> q >> s;
    set<pii> seg;
    for(int i = 0; i < n; i++){
        if(s[i] == '1'){
            int l = i;
            while(i + 1 < n && s[i + 1] == '1') i++;
            seg.emplace(l, i);
            updates.push_back({0, l, i, 1});
        }
    }

    int qc = 0;
    vi qtime;
    for(int t = 1; t <= q; t++){
        cin >> type;
        if(type == "toggle"){
            int i;
            cin >> i;
            if(s[--i] == '0'){
                int l = i, r = i;
                auto right = seg.lower_bound({i, i});
                if(right != seg.end() && right->fi == i + 1){
                    r = right->se;
                    updates.push_back({t, i + 1, r, -1});
                    seg.erase(right);
                }

                auto left = seg.lower_bound({i, i});
                if(left != seg.begin()) left--;
                if(left != seg.end() && left->se == i - 1){
                    l = left->fi;
                    updates.push_back({t, l, i - 1, -1});
                    seg.erase(left);
                }
                seg.emplace(l, r);
                updates.push_back({t, l, r, 1});
                s[i] = '1';
            }
            else{
                auto it = prev(seg.lower_bound({i + 1, i + 1}));
                int l = it->fi, r = it->se;
                seg.erase(it);
                updates.push_back({t, l, r, -1});
                if(l < i){
                    updates.push_back({t, l, i - 1, 1});
                    seg.emplace(l, i - 1);
                }
                if(r > i){
                    updates.push_back({t, i + 1, r, 1});
                    seg.emplace(i + 1, r);
                }
                s[i] = '0';
            }
        }
        else{
            int ql, qr;
            cin >> ql >> qr;
            updates.push_back({t, ql, qr - 3, 0, qc++}); // qr - 3 ?
            qtime.emplace_back(t);
        }
    }
    sort(updates.begin(), updates.end());
    onans.resize(qc), offans.resize(qc);

    cdq(0, sz(updates));
    for(int i = 0; i < qc; i++){
        int ans = offans[i].fi - onans[i].fi;
        if(onans[i].se > offans[i].se) ans += qtime[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