oj.uz

Submission #485367

# Submission time Handle Problem Language Result Execution time Memory
485367 2021-11-07T10:29:03 Z blue Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 3040 KB 
#include "elephants.h"
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 50'000;

int N;
int L;
int* X;
int* I;

void init(int N_, int L_, int X_[])
{
    N = N_;
    L = L_;
    X = new int[N];
    for(int i = 0; i < N; i++) X[i] = X_[i];

    I = new int[N];
    for(int i = 0; i < N; i++) I[i] = i;
}

int update(int i, int y)
{
    int oldX = X[i];
    X[i] = y;

    if(X[i] > oldX)
    {
        for(int j = 0; j+1 < N; j++)
        {
            if(X[I[j]] > X[I[j+1]])
                swap(I[j], I[j+1]);
        }
    }
    else
    {
        for(int j = N-2; j >= 0; j--)
        {
            if(X[I[j]] > X[I[j+1]])
                swap(I[j], I[j+1]);
        }
    }

    int ans = 0;
    int st = -1'000'000'001;

    for(int j = 0; j < N; j++)
    {
        if(X[I[j]] - st > L)
        {
            st = X[I[j]];
            ans++;
        }
    }

    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 2485 ms 1020 KB Output is correct
8 Correct 3575 ms 2100 KB Output is correct
9 Correct 3983 ms 3040 KB Output is correct
10 Correct 8251 ms 2824 KB Output is correct
11 Correct 8246 ms 2760 KB Output is correct
12 Execution timed out 9040 ms 2860 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 2485 ms 1020 KB Output is correct
8 Correct 3575 ms 2100 KB Output is correct
9 Correct 3983 ms 3040 KB Output is correct
10 Correct 8251 ms 2824 KB Output is correct
11 Correct 8246 ms 2760 KB Output is correct
12 Execution timed out 9040 ms 2860 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 2485 ms 1020 KB Output is correct
8 Correct 3575 ms 2100 KB Output is correct
9 Correct 3983 ms 3040 KB Output is correct
10 Correct 8251 ms 2824 KB Output is correct
11 Correct 8246 ms 2760 KB Output is correct
12 Execution timed out 9040 ms 2860 KB Time limit exceeded
13 Halted 0 ms 0 KB -