oj.uz

답안 #18718

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
18718 2016-02-14T17:33:21 Z ggoh 코끼리 (Dancing Elephants) (IOI11_elephants) C++
97 / 100
 1662 ms 27640 KB 
#include<cstdio>
#include<vector>
#include<algorithm>
int a,b,sq,t,how,dpsz,z[150002],x[150002],yy[150002],D[391][2002],len[391][2002],LEN[391][2002],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--;
    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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 27640 KB Output is correct
2 Correct 0 ms 27640 KB Output is correct
3 Correct 0 ms 27640 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 27640 KB Output is correct
2 Correct 0 ms 27640 KB Output is correct
3 Correct 0 ms 27640 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 342 ms 27640 KB Output is correct
2 Correct 417 ms 27640 KB Output is correct
3 Correct 634 ms 27640 KB Output is correct
4 Correct 630 ms 27640 KB Output is correct
5 Correct 493 ms 27640 KB Output is correct
6 Correct 851 ms 27640 KB Output is correct
7 Correct 640 ms 27640 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 411 ms 27640 KB Output is correct
2 Correct 692 ms 27640 KB Output is correct
3 Correct 1291 ms 27640 KB Output is correct
4 Correct 1591 ms 27640 KB Output is correct
5 Correct 1662 ms 27640 KB Output is correct
6 Correct 1221 ms 27640 KB Output is correct
7 Correct 1593 ms 27640 KB Output is correct
8 Correct 1562 ms 27640 KB Output is correct
9 Correct 1178 ms 27640 KB Output is correct

Subtask #5
0.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 113 ms 27636 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -