Submission #403186

#	Time	Username	Problem	Language	Result	Execution time	Memory
403186		AmineTrabelsi	Street Lamps (APIO19_street_lamps)	C++14	40 / 100	1829 ms	524292 KiB

street_lamps

#include <bits/stdc++.h>
using namespace std;
// Hi
int n,q;
string s;
vector<pair<int,pair<int,int>>> que; // 0 toggle 1 query
void sub_one(){
    vector<vector<int>> cnt(n+5,vector<int>(n+5,0));
    vector<int> pref(n+5,0);
    for(int i=0;i<n;i++){
        pref[i+1] = pref[i]+(s[i]=='1');
    }
    for(int i=0;i<=n;i++){
        for(int j=0;j<i;j++){
            cnt[i][j] = cnt[j][i] = (pref[i]-pref[j] == i-j);
        }
    }
    for(int tt=0;tt<q;tt++){
        if(que[tt].first == 0){
            int ind = que[tt].second.first;
            if(s[ind] == '0')s[ind] = '1';
            else s[ind] = '0';
            for(int i=0;i<n;i++){
                pref[i+1] = pref[i]+(s[i]=='1');
            }
        }else{
            int a = que[tt].second.first,b = que[tt].second.second;
            cout << cnt[a][b] << '\n';
        }
        for(int i=0;i<=n;i++){
            for(int j=0;j<i;j++){
                cnt[i][j] = cnt[j][i] += (pref[i]-pref[j] == i-j);
            }
        }
    }
}
void sub_two(){
    vector<int> cnt,last_on(n+1,0);
    for(auto i:s)cnt.push_back(i-'0');
    vector<bool> on(cnt.begin(),cnt.end());
    for(int i=0;i<n;i++){
        if(on[i]){
            last_on[i] = -1;
        }else last_on[i] = 1e9+7;
    }
    for(int time=0;time<q;time++){
        if(que[time].first == 0){
            int ind = que[time].second.first;
            if(!on[ind]){
                on[ind] = 1;
                last_on[ind] = time;
                cnt[ind]++;
            }else{
                int pre = time-last_on[ind]-1;
                cnt[ind] += (pre >= 0 ? pre : 0);
                last_on[ind] = 1e9+7;
                on[ind] = 0;
            }
        }else{
            int a = que[time].second.first;
            int pre = time-last_on[a]-1;
            cout << cnt[a]+(pre >= 0 ? pre : 0) << '\n';
        }
    }
}
void sub_four(){
    // later
}
void sub_three(){
    // later
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>q>>s;
    vector<bool> on;
    for(auto i:s)on.push_back((i=='1' ? 1 : 0));
    bool two = 1,three = 0,four = 0; /// turn these back on
    bool ex = 0;
    for(int i=0;i<q;i++){
        string t;
        cin>>t;
        if(t == "toggle"){
            if(ex)four = 0;
            int ind;
            cin>>ind;
            if(on[ind]){
                three = 0;
                on[ind] = 0;
            }else on[ind] = 1;
            que.push_back({0,{ind-1,0}});
        }else{
            ex = 1;
            int a,b;
            cin>>a>>b;
            if(b-a != 1)two = 0;
            que.push_back({1,{a-1,b-1}});
        }
    }
    if(two){
        sub_two();
    }else if(four){
        sub_four();
    }else if(three){
        sub_three();
    }else sub_one();
    return 0;
}

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