oj.uz

Submission #1051195

# Submission time Handle Problem Language Result Execution time Memory
1051195 2024-08-09T23:10:56 Z oscar1f Dancing Elephants (IOI11_elephants) C++17
10 / 100
 1 ms 8652 KB 
#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});
    }
    dansBloc[nbBloc-1].push_back({-1,2*INFINI,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-1;
}

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8652 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8652 KB Output is correct
4 Incorrect 1 ms 8536 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8652 KB Output is correct
4 Incorrect 1 ms 8536 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8652 KB Output is correct
4 Incorrect 1 ms 8536 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8652 KB Output is correct
4 Incorrect 1 ms 8536 KB Output isn't correct
5 Halted 0 ms 0 KB -