Submission #1234168

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234168		oscar1f	Street Lamps (APIO19_street_lamps)	C++17	20 / 100	5091 ms	28372 KiB

street_lamps

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

#define int long long

struct inter {
    int debInter,finInter,typeInter,dateDeb;
    bool operator < (const inter& autre) const {
        if (debInter!=autre.debInter) {
            return debInter < autre.debInter;
        }
        return finInter < autre.finInter;
    }
};

struct passage {
    int debInter,finInter,duree,dateFin;
};

const int MAX_VAL=300*1000+5,INFINI=1000*1000*1000;
int nbVal,nbReq;
int etatCour[MAX_VAL];
set<inter> enCours;
vector<passage> dejaFini;

void maj(inter ancien,int nouvDate) {
    enCours.erase(ancien);
    if (nouvDate>ancien.dateDeb && ancien.typeInter==1) {
        dejaFini.push_back({ancien.debInter,ancien.finInter,nouvDate-ancien.dateDeb,nouvDate});
    }
}

void modif(int pos,int nouvDate) {
    auto it=enCours.lower_bound({pos,INFINI,0,0});
    it--;
    inter ancien=(*it);
    maj(ancien,nouvDate);
    int nouvDeb=pos,nouvFin=pos;
    if (ancien.debInter<pos) {
        enCours.insert({ancien.debInter,pos-1,ancien.typeInter,nouvDate});
    }
    else if (pos>1) {
        it=enCours.lower_bound({pos,INFINI,0,0});
        it--;
        auto preced=(*it);
        nouvDeb=preced.debInter;
        maj(preced,nouvDate);
    }
    if (ancien.finInter>pos) {
        enCours.insert({pos+1,ancien.finInter,ancien.typeInter,nouvDate});
    }
    else if (pos<nbVal) {
        it=enCours.lower_bound({pos,INFINI,0,0});
        auto suiv=(*it);
        nouvFin=suiv.finInter;
        maj(suiv,nouvDate);
    }
    enCours.insert({nouvDeb,nouvFin,1-ancien.typeInter,nouvDate});
}
 
void afficher() {
    return;
    for (inter i:enCours) {
        cout<<i.debInter<<" "<<i.finInter<<" "<<i.typeInter<<" "<<i.dateDeb<<endl;
    }
    cout<<endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbVal>>nbReq;
    enCours.insert({1,nbVal,0,0});
    for (int i=1;i<=nbVal;i++) {
        char nouv;
        cin>>nouv;
        if (nouv=='1') {
            modif(i,0);
        }
    }
    afficher();
    for (int i=1;i<=nbReq;i++) {
        string typeOp;
        cin>>typeOp;
        if (typeOp=="query") {
            int debReq,finReq,ans=0;
            cin>>debReq>>finReq;
            finReq--;
            auto it=enCours.lower_bound({debReq,INFINI,0,0});
            it--;
            if ((*it).finInter>=finReq && (*it).typeInter==1) {
                ans+=i-(*it).dateDeb;
            }
            for (auto j:dejaFini) {
                if (j.debInter<=debReq && j.finInter>=finReq) {
                    ans+=j.duree;
                }
            }
            cout<<ans<<"\n";
        }
        else {
            int posModif;
            cin>>posModif;
            modif(posModif,i);
            afficher();
        }
    }
}

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