Submission #8036

#	Time	Username	Problem	Language	Result	Execution time	Memory
8036		baneling100	Dancing Elephants (IOI11_elephants)	C++98	100 / 100	6292 ms	24068 KiB

elephants

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

using namespace std;

int N, L, BucketNum, BucketLimit, Bucket[2][400][800], Size[400], Loc[150000][2];
int Next[400][800], Cnt[400][800], Temp[150000][2], Num;

void GiveInfo(int X) {

    int BucketNow=Size[X];

    if(!Size[X])
        return;
    Next[X][Size[X]-1]=Bucket[0][X][Size[X]-1]+L;
    Cnt[X][Size[X]-1]=1;
    for(int i=Size[X]-2 ; i>=0 ; i--) {
        while(Bucket[0][X][i]+L<Bucket[0][X][BucketNow-1]) BucketNow--;
        if(BucketNow==Size[X]) {
            Next[X][i]=Bucket[0][X][i]+L;
            Cnt[X][i]=1;
        }
        else {
            Next[X][i]=Next[X][BucketNow];
            Cnt[X][i]=Cnt[X][BucketNow]+1;
        }
    }
}

void ReArrange(void) {

    int TempSize=0, BucketNow=0;

    for(int i=0 ; i<BucketNum ; i++) {
        for(int j=0 ; j<Size[i] ; j++) {
            Temp[TempSize][0]=Bucket[0][i][j];
            Temp[TempSize][1]=Bucket[1][i][j];
            TempSize++;
        }
        Size[i]=0;
    }
    for(int i=0 ; i<N ; i++) {
        Bucket[0][BucketNow][Size[BucketNow]]=Temp[i][0];
        Bucket[1][BucketNow][Size[BucketNow]]=Temp[i][1];
        Loc[Temp[i][1]][0]=BucketNow;
        Loc[Temp[i][1]][1]=Size[BucketNow];
        Size[BucketNow]++;
        if(Size[BucketNow]==BucketLimit)
            BucketNow++;
    }
    for(int i=0 ; i<BucketNum ; i++)
        GiveInfo(i);
}

void init(int N_, int L_, int X[]) {

    int BucketNow=0;

    N=N_;
    L=L_;
    BucketNum=BucketLimit=sqrt(N);
    if(BucketNum*BucketNum!=N) {
        BucketNum++;
        BucketLimit++;
    }
    for(int i=0 ; i<N ; i++) {
        Bucket[0][BucketNow][Size[BucketNow]]=X[i];
        Bucket[1][BucketNow][Size[BucketNow]]=i;
        Loc[i][0]=BucketNow;
        Loc[i][1]=Size[BucketNow];
        Size[BucketNow]++;
        if(Size[BucketNow]==BucketLimit)
            BucketNow++;
    }
    ReArrange();
}

void Delete(int Key) {

    int X=Loc[Key][0], Y=Loc[Key][1];

    for(int i=Y ; i<Size[X]-1 ; i++) {
        Bucket[0][X][i]=Bucket[0][X][i+1];
        Bucket[1][X][i]=Bucket[1][X][i+1];
        Loc[Bucket[1][X][i]][0]=X;
        Loc[Bucket[1][X][i]][1]=i;
    }
    Size[X]--;
    GiveInfo(X);
}

void Insert(int X, int Y) {

    int Key1, Key2;

    for(Key1=0 ; Key1<BucketNum-1 ; Key1++)
        if(Size[Key1] && X<=Bucket[0][Key1][Size[Key1]-1])
            break;
    for(Key2=0 ; Key2<Size[Key1] ; Key2++)
        if(X<=Bucket[0][Key1][Key2])
            break;
    for(int i=Size[Key1] ; i>=Key2+1 ; i--) {
        Bucket[0][Key1][i]=Bucket[0][Key1][i-1];
        Bucket[1][Key1][i]=Bucket[1][Key1][i-1];
        Loc[Bucket[1][Key1][i]][0]=Key1;
        Loc[Bucket[1][Key1][i]][1]=i;
    }
    Bucket[0][Key1][Key2]=X;
    Bucket[1][Key1][Key2]=Y;
    Loc[Y][0]=Key1;
    Loc[Y][1]=Key2;
    Size[Key1]++;
    GiveInfo(Key1);
}

int FindAns(void) {

    int Length=-1, Key, Ans=0;

    for(int i=0 ; i<BucketNum ; i++)
        if(Size[i]) {
            Key=lower_bound(Bucket[0][i],Bucket[0][i]+Size[i],Length+1)-Bucket[0][i];
            if(Key<Size[i]) {
                Ans+=Cnt[i][Key];
                Length=Next[i][Key];
            }
        }
    return Ans;
}

int update(int i, int y) {

    Delete(i);
    Insert(y,i);
    Num++;
    if(!(Num%BucketNum))
        ReArrange();
    return FindAns();
}

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