oj.uz

Submission #8034

# Submission time Handle Problem Language Result Execution time Memory
8034 2014-08-27T09:10:04 Z baneling100 Dancing Elephants (IOI11_elephants) C++
26 / 100
 6184 ms 31416 KB 
#include "elephants.h"
#include <math.h>
#include <algorithm>

using namespace std;

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

void GiveInfo(long long X) {

    long long 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) {

    long long 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[]) {

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

void Delete(long long Key) {

    long long 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(long long X, long long Y) {

    long long 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);
}

long long FindAns(void) {

    long long 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.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 31416 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 572 ms 31416 KB Output is correct
2 Incorrect 36 ms 31416 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6036 ms 31416 KB Output is correct
2 Correct 6160 ms 31416 KB Output is correct
3 Correct 5564 ms 31416 KB Output is correct
4 Correct 6184 ms 31416 KB Output is correct
5 Correct 5616 ms 31416 KB Output is correct
6 Incorrect 48 ms 31416 KB Output isn't correct
7 Halted 0 ms 0 KB -