oj.uz

Submission #1046567

# Submission time Handle Problem Language Result Execution time Memory
1046567 2024-08-06T17:12:37 Z oscar1f Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 8800 KB 
#include<bits/stdc++.h>
#include "elephants.h"
using namespace std;

const int MAX_ELEPH=150*1000+5,INFINI=1000*1000*1000+5;
int nbEleph,taillePhoto;
int posTri[MAX_ELEPH];
int posCour[MAX_ELEPH];

void init(int N, int L, int X[]) {
    nbEleph=N;
    taillePhoto=L;
    for (int i=0;i<nbEleph;i++) {
        posTri[i]=X[i];
        posCour[i]=X[i];
    }
}

int calc() {
    int ans=0,dernDeb=-INFINI;
    for (int i=0;i<nbEleph;i++) {
        if (dernDeb+taillePhoto<posTri[i]) {
            ans++;
            dernDeb=posTri[i];
        }
    }
    return ans;
}

int update(int posModif, int valNouv) {
    int deb=0,fin=nbEleph-1,mid;
    while (deb!=fin) {
        mid=(deb+fin+1)/2;
        if (posTri[mid]<=posCour[posModif]) {
            deb=mid;
        }
        else {
            fin=mid-1;
        }
    }
    int pos=deb;
    posTri[pos]=valNouv;
    posCour[posModif]=valNouv;
    while (pos>0 and posTri[pos]<posTri[pos-1]) {
        swap(posTri[pos-1],posTri[pos]);
        pos--;
    }
    while (pos<nbEleph-1 and posTri[pos]>posTri[pos+1]) {
        swap(posTri[pos],posTri[pos+1]);
        pos++;
    }
    return calc();
}

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 595 ms 8540 KB Output is correct
8 Correct 1340 ms 8692 KB Output is correct
9 Correct 1230 ms 8796 KB Output is correct
10 Correct 2200 ms 8800 KB Output is correct
11 Correct 2143 ms 8800 KB Output is correct
12 Correct 4256 ms 8800 KB Output is correct
13 Correct 2404 ms 8796 KB Output is correct

Subtask #4
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 595 ms 8540 KB Output is correct
8 Correct 1340 ms 8692 KB Output is correct
9 Correct 1230 ms 8796 KB Output is correct
10 Correct 2200 ms 8800 KB Output is correct
11 Correct 2143 ms 8800 KB Output is correct
12 Correct 4256 ms 8800 KB Output is correct
13 Correct 2404 ms 8796 KB Output is correct
14 Correct 857 ms 8792 KB Output is correct
15 Correct 3137 ms 8536 KB Output is correct
16 Execution timed out 9086 ms 8792 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
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 595 ms 8540 KB Output is correct
8 Correct 1340 ms 8692 KB Output is correct
9 Correct 1230 ms 8796 KB Output is correct
10 Correct 2200 ms 8800 KB Output is correct
11 Correct 2143 ms 8800 KB Output is correct
12 Correct 4256 ms 8800 KB Output is correct
13 Correct 2404 ms 8796 KB Output is correct
14 Correct 857 ms 8792 KB Output is correct
15 Correct 3137 ms 8536 KB Output is correct
16 Execution timed out 9086 ms 8792 KB Time limit exceeded
17 Halted 0 ms 0 KB -