oj.uz

Submission #18717

# Submission time Handle Problem Language Result Execution time Memory
18717 2016-02-14T17:30:55 Z ggoh Dancing Elephants (IOI11_elephants) C++
100 / 100
 4915 ms 22044 KB 
#include<cstdio>
#include<vector>
#include<algorithm>
int a,b,sq,t,how,dpsz,z[150002],x[150002],yy[150002],D[391][781],len[391][781],LEN[391][781],sz[391];
void madp(int num)
{
    if(sz[num]==0)return ;
    len[num][sz[num]]=2000000001;
    int q=0;
    for(int j=0;j<sz[num];j++)
    {
        while(len[num][q]<=len[num][j]+b)q++;
        z[j]=q;
    }
    for(int j=sz[num]-1;j>=0;j--)
    {
        if(z[j]==sz[num])
        {
            D[num][j]=1;
            LEN[num][j]=len[num][j]+b;
        }
        else
        {
            D[num][j]=1+D[num][z[j]];
            LEN[num][j]=LEN[num][z[j]];
        }
    }
}
void makedp()
{
    int u=0;
    for(int j=0;j<dpsz;j++)sz[j]=0;
    for(int j=0;j<a;j++)
    {
        if(j!=0&&j%sq==0)u++;
        len[u][sz[u]++]=yy[j];
    }
    for(int j=0;j<dpsz;j++)
    {
        madp(j);
    }
}
void erase(int p)
{
    int o;
    for(int j=0;j<dpsz;j++)
    {
        if(sz[j]&&len[j][0]<=p&&p<=len[j][sz[j]-1])
        {
            o=j;
            break;
        }
    }
    for(int j=0;j<sz[o];j++)
    {
        if(len[o][j]==p)
        {
            for(int k=j+1;k<sz[o];k++)
            {
                len[o][k-1]=len[o][k];
            }
            break;
        }
    }
    sz[o]--;
    if(sz[o])madp(o);
}
void add(int p)
{
    int o=-1;
    for(int j=0;j<dpsz;j++)
    {
        if(sz[j]&&len[j][0]<=p)o=j;
    }
    if(o==-1)
    {
        for(int j=0;j<dpsz;j++)
        {
            if(sz[j])
            {
                o=j;
                break;
            }
        }
    }
    if(len[o][sz[o]-1]<=p)len[o][sz[o]]=p,sz[o]++;
    else
    {
        for(int j=0;j<sz[o];j++)
        {
            if(len[o][j]>=p)
            {
                for(int k=sz[o];k>j;k--)
                {
                    len[o][k]=len[o][k-1];
                }
                len[o][j]=p;
                break;
            }
        }
        sz[o]++;
    }
    madp(o);
}
void init(int N,int L,int X[])
{
    a=N;
    b=L;
    sq=0;
    for(;sq*sq<=a;sq++);
    sq--;
    dpsz=(a+sq-1)/sq;
    for(int i=0;i<a;i++)yy[i]=X[i],x[i]=X[i];
    makedp();
}
int update(int i,int y)
{
    if(x[i]!=y)
    {
        erase(x[i]);
        x[i]=y;
        add(y);
    }

    int ans=0,l=-1,P,Q,H;
    for(int j=0;j<dpsz;j++)
    {
        if(sz[j]==0)continue;
        if(len[j][sz[j]-1]<=l)continue;
        P=-1;
        Q=sz[j]-1;
        while(P!=Q-1)
        {
            H=(P+Q)/2;
            if(len[j][H]<=l)P=H;
            else Q=H;
        }
        l=LEN[j][Q];
        ans+=D[j][Q];
    }
    how++;
    if(how%sq==0)
    {
        t=0;
        for(int j=0;j<dpsz;j++)
        {
            for(int k=0;k<sz[j];k++)
            {
                yy[t++]=len[j][k];
            }
        }
        makedp();
    }
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 22044 KB Output is correct
2 Correct 414 ms 22044 KB Output is correct
3 Correct 615 ms 22044 KB Output is correct
4 Correct 551 ms 22044 KB Output is correct
5 Correct 444 ms 22044 KB Output is correct
6 Correct 815 ms 22044 KB Output is correct
7 Correct 564 ms 22044 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 418 ms 22044 KB Output is correct
2 Correct 691 ms 22044 KB Output is correct
3 Correct 1237 ms 22044 KB Output is correct
4 Correct 1436 ms 22044 KB Output is correct
5 Correct 1485 ms 22044 KB Output is correct
6 Correct 1061 ms 22044 KB Output is correct
7 Correct 1435 ms 22044 KB Output is correct
8 Correct 1401 ms 22044 KB Output is correct
9 Correct 963 ms 22044 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4143 ms 22044 KB Output is correct
2 Correct 4365 ms 22044 KB Output is correct
3 Correct 3470 ms 22044 KB Output is correct
4 Correct 3677 ms 22044 KB Output is correct
5 Correct 4015 ms 22044 KB Output is correct
6 Correct 727 ms 22044 KB Output is correct
7 Correct 661 ms 22044 KB Output is correct
8 Correct 724 ms 22044 KB Output is correct
9 Correct 686 ms 22044 KB Output is correct
10 Correct 2895 ms 22044 KB Output is correct
11 Correct 2317 ms 22044 KB Output is correct
12 Correct 3323 ms 22044 KB Output is correct
13 Correct 2282 ms 22044 KB Output is correct
14 Correct 892 ms 22044 KB Output is correct
15 Correct 4030 ms 22044 KB Output is correct
16 Correct 3378 ms 22044 KB Output is correct
17 Correct 3623 ms 22044 KB Output is correct
18 Correct 3361 ms 22044 KB Output is correct
19 Correct 4879 ms 22044 KB Output is correct
20 Correct 4915 ms 22044 KB Output is correct