oj.uz

Submission #18719

# Submission time Handle Problem Language Result Execution time Memory
18719 2016-02-14T17:34:43 Z ggoh Dancing Elephants (IOI11_elephants) C++
100 / 100
 7351 ms 25096 KB 
#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.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 25096 KB Output is correct
2 Correct 414 ms 25096 KB Output is correct
3 Correct 638 ms 25096 KB Output is correct
4 Correct 614 ms 25096 KB Output is correct
5 Correct 487 ms 25096 KB Output is correct
6 Correct 840 ms 25096 KB Output is correct
7 Correct 640 ms 25096 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 25096 KB Output is correct
2 Correct 688 ms 25096 KB Output is correct
3 Correct 1292 ms 25096 KB Output is correct
4 Correct 1602 ms 25096 KB Output is correct
5 Correct 1668 ms 25096 KB Output is correct
6 Correct 1256 ms 25096 KB Output is correct
7 Correct 1606 ms 25096 KB Output is correct
8 Correct 1562 ms 25096 KB Output is correct
9 Correct 1225 ms 25096 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 6677 ms 25096 KB Output is correct
2 Correct 6926 ms 25096 KB Output is correct
3 Correct 5666 ms 25096 KB Output is correct
4 Correct 6278 ms 25096 KB Output is correct
5 Correct 6628 ms 25096 KB Output is correct
6 Correct 738 ms 25096 KB Output is correct
7 Correct 677 ms 25096 KB Output is correct
8 Correct 726 ms 25096 KB Output is correct
9 Correct 671 ms 25096 KB Output is correct
10 Correct 4152 ms 25096 KB Output is correct
11 Correct 3777 ms 25096 KB Output is correct
12 Correct 5512 ms 25096 KB Output is correct
13 Correct 3842 ms 25096 KB Output is correct
14 Correct 1679 ms 25096 KB Output is correct
15 Correct 6304 ms 25096 KB Output is correct
16 Correct 5502 ms 25096 KB Output is correct
17 Correct 5826 ms 25096 KB Output is correct
18 Correct 5460 ms 25096 KB Output is correct
19 Correct 7319 ms 25096 KB Output is correct
20 Correct 7351 ms 25096 KB Output is correct