Submission #403207

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

street_lamps

// subtasks will not match always 
#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_three(){
    // every lamp is becoming on
    cout<<"Wrong answer\n";
}
const int M = 300005;
int tree[M*4+50];
void build(int v,int tl,int tr){
    if(tl == tr){
        tree[v] = (s[tr] == '1' ? 0 : 1e9+7);
        return;
    }
    int mid = (tl+tr)/2;
    build(v*2,tl,mid);
    build(v*2+1,mid+1,tr);
    tree[v] = max(tree[v*2],tree[v*2+1]);
}
void upd(int v,int tl,int tr,int ind,int val){
    if(tl == tr && tl == ind){
        //cout<<v<<" "<<tl<<" "<<tr<<endl;
        tree[v] = val;
        return;
    }if(tl == tr)return;//will not happen but just in case
    int mid = (tl+tr)/2;
    if(ind <= mid){
        upd(v*2,tl,mid,ind,val);
    }else upd(v*2+1,mid+1,tr,ind,val);
    tree[v] = max(tree[v*2],tree[v*2+1]);
}
int mx(int v,int tl,int tr,int ql,int qr){
    if(ql > qr || tl > qr || tr < ql)return -(1e9+7);
    if(ql == tl && tr == qr){
        return tree[v];
    }if(tl == tr)return -(1e9+7);
    int mid = (tl+tr)/2;
    return max(mx(v*2,tl,mid,ql,min(mid,qr)),mx(v*2+1,mid+1,tr,max(mid+1,ql),qr));
}
void sub_four(){
    // max segment tree
    build(1,0,n-1);
    for(int time=0;time<q;time++){
        if(que[time].first == 0){
            int ind = que[time].second.first;
            upd(1,0,n-1,ind,time+1);
        }else{
            int a = que[time].second.first,b = que[time].second.second;
            int ans =  time-mx(1,0,n-1,a,b-1)+1;
            cout << (ans >= 0 ? ans : 0) << '\n';
        }
    }
}
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 one = (n <= 200),two = 1,three = 0,four = 1;
    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}});
        }
    }/*
    sub_four();
    */
    if(one){
        sub_one();
    }else if(two){
        sub_two();
    }else if(four){
        sub_four();
    }else if(three)sub_three();
    else sub_one();
    
    return 0;
}
/*
5 7
11011
toggle 3
query 1 2
query 1 2
query 1 6
query 3 4
query 3 4
query 1 6

*/

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