Submission #1234286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234286		oscar1f	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	5109 ms	486652 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;
};

struct noeud {
    int decalage=1;
    set<int> toutNum;
    unordered_map<int,int> corres;
    vector<int> som;
};

const int MAX_VAL=300*1000+5,INFINI=1000*1000*1000,DECA=(1<<19);
int nbVal,nbReq;
int rep[MAX_VAL];
int quest[MAX_VAL][2];
int etatCour[MAX_VAL];
set<inter> enCours;
vector<passage> ajout[MAX_VAL];
noeud arb[2*DECA];

void maj(inter ancien,int nouvDate) {
    enCours.erase(ancien);
    if (nouvDate>ancien.dateDeb && ancien.typeInter==1) {
        ajout[nouvDate].push_back({ancien.debInter,ancien.finInter,nouvDate-ancien.dateDeb});
        //cout<<"!"<<nouvDate<<" : "<<ancien.debInter<<" "<<ancien.finInter<<" "<<nouvDate-ancien.dateDeb<<endl;
    }
}

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;
}

void marqueAjout(passage nouv) {
    int pos=DECA+nouv.debInter;
    while (pos>0) {
        arb[pos].toutNum.insert(nouv.finInter);
        pos/=2;
    }
}

void marqueQuest(int deb,int fin,int finReq) {
    if (deb==fin) {
        arb[deb].toutNum.insert(finReq);
        return;
    }
    if (deb%2==1) {
        arb[deb].toutNum.insert(finReq);
        marqueQuest(deb+1,fin,finReq);
        return;
    }
    if (fin%2==0) {
        arb[fin].toutNum.insert(finReq);
        marqueQuest(deb,fin-1,finReq);
        return;
    }
    marqueQuest(deb/2,fin/2,finReq);
}

void ajoutInter(passage nouv) {
    int pos=DECA+nouv.debInter;
    while (pos>0) {
        int temp=arb[pos].corres[nouv.finInter]+arb[pos].decalage;
        while (temp>0) {
            arb[pos].som[temp]+=nouv.duree;
            temp/=2;
        }
        pos/=2;
    }
}

int calcSom(int deb,int fin,int idSom) {
    if (deb==fin) {
        return arb[idSom].som[deb];
    }
    if (deb%2==1) {
        return arb[idSom].som[deb]+calcSom(deb+1,fin,idSom);
    }
    if (fin%2==0) {
        return arb[idSom].som[fin]+calcSom(deb,fin-1,idSom);
    }
    return calcSom(deb/2,fin/2,idSom);
}

int calcQuest(int deb,int fin,int finReq) {
    if (deb==fin) {
        return calcSom(arb[deb].decalage+arb[deb].corres[finReq],2*arb[deb].decalage-1,deb);
    }
    if (deb%2==1) {
        return calcSom(arb[deb].decalage+arb[deb].corres[finReq],2*arb[deb].decalage-1,deb)+calcQuest(deb+1,fin,finReq);
    }
    if (fin%2==0) {
        return calcSom(arb[fin].decalage+arb[fin].corres[finReq],2*arb[fin].decalage-1,fin)+calcQuest(deb,fin-1,finReq);
    }
    return calcQuest(deb/2,fin/2,finReq);
}

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;
            cin>>debReq>>finReq;
            finReq--;
            quest[i][0]=debReq;
            quest[i][1]=finReq;
            auto it=enCours.lower_bound({debReq,INFINI,0,0});
            it--;
            if ((*it).finInter>=finReq && (*it).typeInter==1) {
                rep[i]+=i-(*it).dateDeb;
                //cout<<i<<" : "<<rep[i]<<endl;
            }
        }
        else {
            int posModif;
            cin>>posModif;
            modif(posModif,i);
            afficher();
        }
    }
    for (int i=1;i<=nbReq;i++) {
        if (quest[i][0]==0) {
            for (passage j:ajout[i]) {
                marqueAjout(j);
            }
        }
        else {
            marqueQuest(DECA,DECA+quest[i][0],quest[i][1]);
        }
    }
    for (int i=0;i<2*DECA;i++) {
        int num=0;
        for (int j:arb[i].toutNum) {
            arb[i].corres[j]=num;
            num++;
        }
        while (arb[i].decalage<num) {
            arb[i].decalage*=2;
        }
        arb[i].som.resize(2*arb[i].decalage,0);
        arb[i].toutNum.clear();
        //cout<<i<<" : "<<num<<" "<<arb[i].decalage<<endl;
    }
    for (int i=1;i<=nbReq;i++) {
        if (quest[i][0]==0) {
            for (passage j:ajout[i]) {
                //cout<<i<<" : "<<j.debInter<<" "<<j.finInter<<" "<<j.duree<<endl;
                ajoutInter(j);
            }
        }
        else {
            rep[i]+=calcQuest(DECA,DECA+quest[i][0],quest[i][1]);
        }
    }
    for (int i=1;i<=nbReq;i++) {
        if (quest[i][0]!=0) {
            cout<<rep[i]<<"\n";
        }
    }
}

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