Submission #1234269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234269		inesfi	Street Lamps (APIO19_street_lamps)	C++20	20 / 100	115 ms	5680 KiB

street_lamps

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define endl "\n"

const int DECA=(1<<20),INFINI=1000*1000*1000;
int arbre[2*DECA];
int nblampes,nbreq;

int maxi(int a,int b){
    if (a==b){
        return arbre[a];
    }
    if (a%2==1){
        return max(arbre[a],maxi(a+1,b));
    }
    if (b%2==0){
        return max(maxi(a,b-1),arbre[b]);
    }
    return maxi(a/2,b/2);
}

void modif(int a){
    while (a>0){
        a/=2;
        arbre[a]=max(arbre[2*a],arbre[2*a+1]);
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>nblampes>>nbreq;
    for (int i=0;i<nblampes;i++){
        char c;
        cin>>c;
        if (c=='0'){
            arbre[i+DECA]=INFINI;
        }
    }
    for (int i=0;i<nblampes;i++){
        modif(i+DECA);
    }
    for (int i=1;i<=nbreq;i++){
        string type;
        cin>>type;
        if (type=="toggle"){
            int place;
            cin>>place;
            place--;
            arbre[place+DECA]=i;
            modif(place+DECA);
        }
        else {
            int deb,fin;
            cin>>deb>>fin;
            deb--;
            fin--;
            int m=maxi(deb+DECA,fin+DECA-1);
            if (m==INFINI){
                cout<<0<<endl;
            }
            else {
                cout<<i-m<<endl;
            }
        }
    }
    //cout<<total[4]<<endl;
    return 0;
}

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