Submission #551828

#	Time	Username	Problem	Language	Result	Execution time	Memory
551828		Jarif_Rahman	Street Lamps (APIO19_street_lamps)	C++17	100 / 100	1596 ms	47768 KiB

street_lamps

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

struct BIT{
    int n;
    vector<ll> sm;
    BIT(int _n){
        n = _n;
        sm.resize(n);
    }
    void add(int in, ll x){
        in++;
        while(in <= n) sm[in-1]+=x, in+=in&-in;
    }
    ll sum(int in){
        in++;
        ll s = 0;
        while(in >= 1) s+=sm[in-1], in-=in&-in;
        return s;
    }
    ll sum(int l, int r){
        return sum(r)-(l == 0? 0:sum(l-1));
    }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q; cin >> n >> q;
    str s; cin >> s;

    set<tuple<int, int, int>> segments;
    vector<tuple<int, int, int, int>> queries;
    vector<ll> ans;
    vector<int> qqtt;

    int ls = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == '0'){
            if(ls < i){
                segments.insert({ls, i-1, 0});
                queries.pb({ls, 1, i-1, 0});
            }
            ls = i+1;
        }
    }
    if(ls != n){
        segments.insert({ls, n-1, 0});
        queries.pb({ls, 1, n-1, 0});
    }

    for(int qq = 1; qq <= q; qq++){
        str tt; cin >> tt;
        if(tt == "toggle"){
            int i; cin >> i; i--;
            if(s[i] == '0'){
                auto it = segments.lower_bound(make_tuple(i, 0, 0));
                if(it != segments.end() && get<0>(*it) == i+1 &&
                    it != segments.begin() && get<1>(*prev(it)) == i-1){
                    auto [l, r0, t1] = *prev(it);
                    auto [l0, r, t2] = *it;

                    it = segments.erase(prev(it));
                    segments.erase(it);
                    queries.pb({l, 2, r0, t1});
                    queries.pb({l0, 2, r, t2});

                    queries.pb({l, 0, r0, qq-t1});
                    queries.pb({l0, 0, r, qq-t2});

                    segments.insert({l, r, qq});
                    queries.pb({l, 1, r, qq});
                }
                else if(it != segments.end() && get<0>(*it) == i+1){
                    auto [l, r, t] = *it;

                    segments.erase(it);
                    queries.pb({l, 2, r, t});

                    queries.pb({l, 0, r, qq-t});

                    segments.insert({l-1, r, qq});
                    queries.pb({l-1, 1, r, qq});
                }
                else if(it != segments.begin() && get<1>(*prev(it)) == i-1){
                    it = prev(it);
                    auto [l, r, t] = *it;

                    segments.erase(it);
                    queries.pb({l, 2, r, t});

                    queries.pb({l, 0, r, qq-t});

                    segments.insert({l, r+1, qq});
                    queries.pb({l, 1, r+1, qq});
                }
                else{
                    segments.insert({i, i, qq});
                    queries.pb({i, 1, i, qq});
                }
                s[i] = '1';
            }
            else{
                auto it = segments.lower_bound(make_tuple(i, -1, -1));
                if(it == segments.end() || get<0>(*it) != i) it--;
                auto [l, r, t] = *it;

                segments.erase(it);
                queries.pb({l, 2, r, t});

                queries.pb({l, 0, r, qq-t});

                if(l != i) segments.insert({l, i-1, qq}), queries.pb({l, 1, i-1, qq});
                if(r != i) segments.insert({i+1, r, qq}), queries.pb({i+1, 1, r, qq});
                s[i] = '0';
            }
        }
        else{
            int a, b; cin >> a >> b; a--, b-=2;
            queries.pb({a, 3, b, ans.size()});
            ans.pb(0);
            qqtt.pb(qq);
        }
    }

    BIT bit1(n), bit2(n), bit3(n);

    function<void(int, int)> cdq_dnc = [&](int l, int r){
        if(l == r) return;
        int md = (l+r)/2;
        cdq_dnc(l, md);
        cdq_dnc(md+1, r);
        vector<tuple<int, int, int, int>> sth;
        for(int i = l; i <= md; i++) if(get<1>(queries[i]) != 3) sth.pb(queries[i]);  
        for(int i = md+1; i <= r; i++) if(get<1>(queries[i]) == 3) sth.pb(queries[i]);
        sort(sth.begin(), sth.end());

        for(auto [l, t, r, c]: sth){
            if(t == 0) bit1.add(r, c);
            else if(t == 1) bit2.add(r, 1), bit3.add(r, c);
            else if(t == 2) bit2.add(r, -1), bit3.add(r, -c);
            else{
                ans[c]+=bit1.sum(r, n-1);
                ans[c]+=bit2.sum(r, n-1)*qqtt[c]-bit3.sum(r, n-1);
            }
        }
        for(auto [l, t, r, c]: sth){
            if(t == 0) bit1.add(r, -c);
            else if(t == 1) bit2.add(r, -1), bit3.add(r, -c);
            else if(t == 2) bit2.add(r, 1), bit3.add(r, c);
        }
    };

    cdq_dnc(0, int(queries.size())-1);

    for(ll x: ans) cout << x << "\n";
}

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