oj.uz

Submission #1051204

# Submission time Handle Problem Language Result Execution time Memory
1051204 2024-08-09T23:39:17 Z oscar1f Dancing Elephants (IOI11_elephants) C++17
100 / 100
 7294 ms 23192 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++) {
        blocCour[elephTri[i].second]=i/tailleBloc;
        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;
}

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 (dansBloc[blocAjout].empty() or valNouv>dansBloc[blocAjout].back().posEleph)) {
        blocAjout++;
    }
    blocCour[posModif]=blocAjout;
    if (dansBloc[blocAjout].empty() or 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();
    }
    /*for (int i=0;i<nbEleph;i++) {
        cout<<posCour[i]<<" ";
    }
    cout<<" : "<<calcRep()<<endl;*/
    return calcRep();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 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 8536 KB Output is correct
2 Correct 1 ms 8536 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 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 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 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 373 ms 10164 KB Output is correct
8 Correct 459 ms 10792 KB Output is correct
9 Correct 709 ms 12208 KB Output is correct
10 Correct 760 ms 12184 KB Output is correct
11 Correct 686 ms 11952 KB Output is correct
12 Correct 1229 ms 12100 KB Output is correct
13 Correct 728 ms 11768 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 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 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 373 ms 10164 KB Output is correct
8 Correct 459 ms 10792 KB Output is correct
9 Correct 709 ms 12208 KB Output is correct
10 Correct 760 ms 12184 KB Output is correct
11 Correct 686 ms 11952 KB Output is correct
12 Correct 1229 ms 12100 KB Output is correct
13 Correct 728 ms 11768 KB Output is correct
14 Correct 703 ms 11468 KB Output is correct
15 Correct 792 ms 11328 KB Output is correct
16 Correct 1817 ms 12724 KB Output is correct
17 Correct 2144 ms 14656 KB Output is correct
18 Correct 2190 ms 14508 KB Output is correct
19 Correct 1650 ms 14720 KB Output is correct
20 Correct 2184 ms 14568 KB Output is correct
21 Correct 2136 ms 14540 KB Output is correct
22 Correct 1276 ms 14164 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 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 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 373 ms 10164 KB Output is correct
8 Correct 459 ms 10792 KB Output is correct
9 Correct 709 ms 12208 KB Output is correct
10 Correct 760 ms 12184 KB Output is correct
11 Correct 686 ms 11952 KB Output is correct
12 Correct 1229 ms 12100 KB Output is correct
13 Correct 728 ms 11768 KB Output is correct
14 Correct 703 ms 11468 KB Output is correct
15 Correct 792 ms 11328 KB Output is correct
16 Correct 1817 ms 12724 KB Output is correct
17 Correct 2144 ms 14656 KB Output is correct
18 Correct 2190 ms 14508 KB Output is correct
19 Correct 1650 ms 14720 KB Output is correct
20 Correct 2184 ms 14568 KB Output is correct
21 Correct 2136 ms 14540 KB Output is correct
22 Correct 1276 ms 14164 KB Output is correct
23 Correct 4696 ms 20172 KB Output is correct
24 Correct 5021 ms 20180 KB Output is correct
25 Correct 3897 ms 20424 KB Output is correct
26 Correct 5016 ms 20456 KB Output is correct
27 Correct 5500 ms 20064 KB Output is correct
28 Correct 970 ms 11604 KB Output is correct
29 Correct 909 ms 11848 KB Output is correct
30 Correct 958 ms 11604 KB Output is correct
31 Correct 896 ms 11864 KB Output is correct
32 Correct 4022 ms 19660 KB Output is correct
33 Correct 4148 ms 18988 KB Output is correct
34 Correct 4547 ms 20028 KB Output is correct
35 Correct 4014 ms 23192 KB Output is correct
36 Correct 2390 ms 19628 KB Output is correct
37 Correct 6809 ms 22868 KB Output is correct
38 Correct 4473 ms 19060 KB Output is correct
39 Correct 4944 ms 19900 KB Output is correct
40 Correct 4166 ms 18900 KB Output is correct
41 Correct 7168 ms 19588 KB Output is correct
42 Correct 7294 ms 19832 KB Output is correct