oj.uz

Submission #1051174

# Submission time Handle Problem Language Result Execution time Memory
1051174 2024-08-09T22:07:22 Z oscar1f Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 10300 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;
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.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 8540 KB Output is correct

Subtask #2
16.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 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8652 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct

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 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8652 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Execution timed out 9025 ms 10300 KB Time limit exceeded
8 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 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8652 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Execution timed out 9025 ms 10300 KB Time limit exceeded
8 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 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8652 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Execution timed out 9025 ms 10300 KB Time limit exceeded
8 Halted 0 ms 0 KB -