Submission #1051174

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051174		oscar1f	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9025 ms	10300 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;
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<<dansBloc[idBloc][i].numEleph<<" "<<dansBloc[idBloc][i].posEleph<<" "<<dansBloc[idBloc][i].nbRest<<" "<<dansBloc[idBloc][i].posFin<<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 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) {
    posCour[posModif]=valNouv;
    reconstruire();
    return calcRep();
}

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