Submission #18719

#	Time	Username	Problem	Language	Result	Execution time	Memory
18719		ggoh	Dancing Elephants (IOI11_elephants)	C++98	100 / 100	7351 ms	25096 KiB

elephants

#include<cstdio>
#include<vector>
#include<algorithm>
int a,b,sq,t,how,dpsz,z[150002],x[150002],yy[150002],D[752][752],len[752][752],LEN[752][752],sz[752];
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--;
    if(sq>200)sq=200;
    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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3