Submission #551609

#	Time	Username	Problem	Language	Result	Execution time	Memory
551609		Jarif_Rahman	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5094 ms	8280 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;
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>> old_segments;

    int ls = 0;
    for(int i = 0; i < n; i++){
        if(s[i] == '0'){
            if(ls < i) segments.insert({ls, i-1, 0});
            ls = i+1;
        }
    }
    if(ls != n) segments.insert({ls, 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);
                    old_segments.pb({l, r0, qq-t1});
                    old_segments.pb({l0, r, qq-t2});
                    segments.insert({l, r, qq});
                }
                else if(it != segments.end() && get<0>(*it) == i+1){
                    auto [l, r, t] = *it;
                    segments.erase(it);
                    old_segments.pb({l, r, qq-t});
                    segments.insert({l-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);
                    old_segments.pb({l, r, qq-t});
                    segments.insert({l, r+1, qq});
                }
                else segments.insert({i, 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);
                old_segments.pb({l, r, qq-t});

                if(l != i) segments.insert({l, i-1, qq});
                if(r != i) segments.insert({i+1, r, qq});
                s[i] = '0';
            }
        }
        else{
            int a, b; cin >> a >> b; a--, b-=2;
            int ans = 0;
            for(auto [l, r, t]: old_segments) if(l <= a && r >= b) ans+=t;
            for(auto [l, r, t]: segments) if(l <= a && r >= b) ans+=qq-t;
            cout << ans << "\n";
        }
    }
}

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