제출 #345739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
345739		daniel920712	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	26 / 100	9021 ms	3820 KiB

elephants

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

using namespace std;
int n;
pair < int , int > all[150005];
int Next[150005];
int last[150005];
int cha[1500005];

int where[150005];

int l;
void init(int N, int l, int X[])
{
    int i;
    n = N;
    ::l=l;
    for(i=0;i<N;i++) all[i+1]=make_pair(X[i],i);
    sort(all+1,all+N+1);
    for(i=1;i<=N;i++) where[i]=all[i].first;
    for(i=1;i<=N;i++) cha[all[i].second]=i;
    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=cha[i];
    //printf("%d %d\n",i,y);
    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)
    {
        //printf("%d\n",where[here]);
        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