Submission #345741

#	Time	Username	Problem	Language	Result	Execution time	Memory
345741		daniel920712	Dancing Elephants (IOI11_elephants)	C++14	26 / 100	9010 ms	1760 KiB

elephants

#include "elephants.h"
#include <set>
#include <algorithm>

using namespace std;
int n;
int Next[50005];
int last[50005];
int cha[50005];
int where[50005];

int l;
void init(int N, int l, int X[])
{
    int i;
    n = N;
    ::l=l;
    for(i=1;i<=N;i++) where[i]=X[i-1];

    for(i=0;i<=N;i++) Next[i]=i+1;
    for(i=0;i<=N;i++) last[i]=i-1;
    where[N+1]=2e9;

}

int update(int i, int y)
{
    int now=0,a,b,here,ll;
    i++;
    a=last[i];
    b=Next[i];

    Next[a]=b;
    last[b]=a;

    here=0;
    while(1)
    {
        if(where[Next[here]]>y)
        {
            a=here;
            b=Next[here];
            Next[a]=i;
            Next[i]=b;
            last[b]=i;
            last[i]=a;
            break;
        }
        here=Next[here];
    }

    where[i]=y;
    here=Next[0];
    ll=where[here];
    now=1;

    while(here!=n+1)
    {
        if(where[here]-ll>l)
        {
            now++;
            ll=where[here];
        }
        here=Next[here];
    }

    return now;
}

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3