Submission #485367

#	Time	Username	Problem	Language	Result	Execution time	Memory
485367		blue	Dancing Elephants (IOI11_elephants)	C++17	26 / 100	9040 ms	3040 KiB

elephants

#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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3