Submission #1051190

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051190		oscar1f	Dancing Elephants (IOI11_elephants)	C++17	10 / 100	1 ms	8540 KiB

elephants

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

struct eleph {
    int numEleph,posEleph,nbRest,posFin;
};

const int MAX_ELEPH=150*1000+5,MAX_BLOCS=500,INFINI=1000*1000*1000+5;
int nbEleph,taillePhoto,tailleBloc,nbBloc,idReq;
int posCour[MAX_ELEPH],blocCour[MAX_ELEPH];
vector<eleph> dansBloc[MAX_BLOCS];

void repartir() {
    for (int i=0;i<nbBloc;i++) {
        dansBloc[i].clear();
    }
    vector<pair<int,int>> elephTri;
    for (int i=0;i<nbEleph;i++) {
        elephTri.push_back({posCour[i],i});
    }    
    sort(elephTri.begin(),elephTri.end());
    for (int i=0;i<nbEleph;i++) {
        dansBloc[i/tailleBloc].push_back({elephTri[i].second,elephTri[i].first,0,0});
    }
}

void calcBloc(int idBloc) {
    int deb,fin,mid=0;
    for (int i=(int)dansBloc[idBloc].size()-1;i>=0;i--) {
        if (dansBloc[idBloc][i].posEleph+taillePhoto>=dansBloc[idBloc].back().posEleph) {
            dansBloc[idBloc][i].nbRest=1;
            dansBloc[idBloc][i].posFin=dansBloc[idBloc][i].posEleph+taillePhoto;
            deb=-1;
        }
        else {
            deb=i+1;
            fin=dansBloc[idBloc].size()-1;
            while (deb!=fin) {
                mid=(deb+fin)/2;
                if (dansBloc[idBloc][i].posEleph+taillePhoto>=dansBloc[idBloc][mid].posEleph) {
                    deb=mid+1;
                }
                else {
                    fin=mid;
                }
            }
            dansBloc[idBloc][i].nbRest=dansBloc[idBloc][deb].nbRest+1;
            dansBloc[idBloc][i].posFin=dansBloc[idBloc][deb].posFin;
        }
        //cout<<idBloc<<" "<<dansBloc[idBloc][i].numEleph<<" "<<dansBloc[idBloc][i].posEleph<<" "<<dansBloc[idBloc][i].nbRest<<" "<<dansBloc[idBloc][i].posFin<<endl;
    }
    //cout<<endl;
}

void reconstruire() {
    repartir();
    for (int i=0;i<nbBloc;i++) {
        calcBloc(i);
    }
    //cout<<endl;
}

int calcRep() {
    int ans=0,finCouv=-1,deb,fin,mid;
    for (int i=0;i<nbBloc;i++) {
        if (!dansBloc[i].empty() and finCouv<dansBloc[i].back().posEleph) {
            deb=0;
            fin=dansBloc[i].size()-1;
            while (deb!=fin) {
                mid=(deb+fin)/2;
                if (finCouv<dansBloc[i][mid].posEleph) {
                    fin=mid;
                }
                else {
                    deb=mid+1;
                }
            }
            //cout<<deb<<endl;
            ans+=dansBloc[i][deb].nbRest;
            finCouv=dansBloc[i][deb].posFin;
        }
    } 
    return ans;
}

void supprimer(int posModif) {
    int blocModif=blocCour[posModif];
    vector<eleph> ancien=dansBloc[blocModif];
    dansBloc[blocModif].clear();
    for (eleph i:ancien) {
        if (i.numEleph!=posModif) {
            dansBloc[blocModif].push_back(i);
        }
    }
    //cout<<"-"<<blocModif<<endl;
    calcBloc(blocModif);
}

void ajouter(int posModif,int valNouv) {
    posCour[posModif]=valNouv;
    int blocAjout=0;
    while (blocAjout<nbBloc-1 and valNouv>dansBloc[blocAjout].back().posEleph) {
        blocAjout++;
    }
    blocCour[posModif]=blocAjout;
    if (valNouv>=dansBloc[blocAjout].back().posEleph) {
        dansBloc[blocAjout].push_back({posModif,valNouv,0,0});
    }
    else {
        vector<eleph> ancien=dansBloc[blocAjout];
        dansBloc[blocAjout].clear();
        int dejaAj=0;
        for (eleph i:ancien) {
            if (dejaAj==0 and valNouv<=i.posEleph) {
                dejaAj=1;
                dansBloc[blocAjout].push_back({posModif,valNouv,0,0});
            }
            dansBloc[blocAjout].push_back(i);
        }
    }
    //cout<<"+"<<blocAjout<<endl;
    calcBloc(blocAjout);
}

void init(int N, int L, int X[]) {
    nbEleph=N;
    taillePhoto=L;
    tailleBloc=sqrt(N)+1;
    nbBloc=(nbEleph+tailleBloc-1)/tailleBloc;
    for (int i=0;i<nbEleph;i++) {
        posCour[i]=X[i];
    }
    reconstruire();
}


int update(int posModif, int valNouv) {
    //cout<<"/////////"<<endl;
    //cout<<endl;
    idReq++;
    supprimer(posModif);
    ajouter(posModif,valNouv);
    if (idReq%(tailleBloc-1)==0) {
        reconstruire();
    }
    return calcRep();
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3