oj.uz

Submission #18716

# Submission time Handle Problem Language Result Execution time Memory
18716 2016-02-14T17:27:03 Z ggoh Dancing Elephants (IOI11_elephants) C++
100 / 100
 5788 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)
{
    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 340 ms 22044 KB Output is correct
2 Correct 423 ms 22044 KB Output is correct
3 Correct 605 ms 22044 KB Output is correct
4 Correct 555 ms 22044 KB Output is correct
5 Correct 457 ms 22044 KB Output is correct
6 Correct 802 ms 22044 KB Output is correct
7 Correct 577 ms 22044 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 419 ms 22044 KB Output is correct
2 Correct 682 ms 22044 KB Output is correct
3 Correct 1233 ms 22044 KB Output is correct
4 Correct 1439 ms 22044 KB Output is correct
5 Correct 1484 ms 22044 KB Output is correct
6 Correct 1049 ms 22044 KB Output is correct
7 Correct 1425 ms 22044 KB Output is correct
8 Correct 1395 ms 22044 KB Output is correct
9 Correct 955 ms 22044 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5612 ms 22044 KB Output is correct
2 Correct 5697 ms 22044 KB Output is correct
3 Correct 3487 ms 22044 KB Output is correct
4 Correct 5066 ms 22044 KB Output is correct
5 Correct 5788 ms 22044 KB Output is correct
6 Correct 719 ms 22044 KB Output is correct
7 Correct 685 ms 22044 KB Output is correct
8 Correct 745 ms 22044 KB Output is correct
9 Correct 678 ms 22044 KB Output is correct
10 Correct 3009 ms 22044 KB Output is correct
11 Correct 2324 ms 22044 KB Output is correct
12 Correct 3301 ms 22044 KB Output is correct
13 Correct 2313 ms 22044 KB Output is correct
14 Correct 1477 ms 22044 KB Output is correct
15 Correct 3993 ms 22044 KB Output is correct
16 Correct 3414 ms 22044 KB Output is correct
17 Correct 3622 ms 22044 KB Output is correct
18 Correct 3299 ms 22044 KB Output is correct
19 Correct 4843 ms 22044 KB Output is correct
20 Correct 4869 ms 22044 KB Output is correct