Submission #7568

# Submission time Handle Problem Language Result Execution time Memory
7568 2014-08-11T09:07:20 Z dohyun0324 Dancing Elephants (IOI11_elephants) C++
0 / 100
92 ms 25316 KB
#include "elephants.h"
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
int ix,iy,n,l,m,r,p=1,q,k,a[150010],d[150010],dap,leng[150010],a2[150010];
struct data
{
    int c,x,y,len,val;
}ar[400][800];
void balance(int sx,int sy,int slen)
{
    if(ar[sx][sy].c>slen){
        while(ar[sx][sy].c>slen){
            sy--;
            if(sy==0){sx--; sy=leng[sx];}
            if(ar[sx][sy].c==0){ sx--; sy=leng[sx];}
        }
        sy++;
        if(sy==leng[sx]+1) sx++, sy=1;
    }
    else{
        while(ar[sx][sy].c<=slen){
            if(ar[sx][sy].c==0) sx++, sy=1;
            else{
                sy++;
                if(sy==leng[sx]+1) sx++, sy=1;
            }
        }
    }
    ix=sx; iy=sy;
}
void erase1(int x)
{
    int i,j,*e,pos,b,kx,ky;
    e=upper_bound(d+1,d+p+1,x);
    pos=e-d-1;
    while(!leng[pos]) pos--;
    for(i=1;i<=leng[pos];i++){
        if(ar[pos][i].c==x) break;
    }
    b=i;
    for(i=b;i<=leng[pos];i++){
        ar[pos][i].c=ar[pos][i+1].c; ar[pos][i].x=ar[pos][i+1].x; ar[pos][i].y=ar[pos][i+1].y; ar[pos][i].len=ar[pos][i+1].len; ar[pos][i].val=ar[pos][i+1].val;
    }
    if(b==1){
        d[pos]=ar[pos][1].c;
    }
    leng[pos]--;
    kx=ar[pos][b-1].x; ky=ar[pos][b-1].y;
    if(ky>leng[kx]) ky=leng[kx];
    if(ky==0){kx--; ky=leng[kx];}
    balance(kx,ky,ar[pos][b-1].len);
    kx=ix; ky=iy;
    for(i=b-1;i>=1;i--){
        kx=ix; ky=iy;
        while(ar[kx][ky].c-ar[pos][i].c>l){
            ky--;
            if(ky==0){kx--; ky=leng[kx];}
            if(ar[kx][ky].c==0){ kx--; ky=leng[kx];}
        }
        ky++;
        if(ky==leng[kx]+1){kx++; ky=1;}
        if(kx==p+1){
            ar[pos][i].val=0;
            continue;
        }
        if(kx>pos){
            ar[pos][i].x=kx;
            ar[pos][i].y=ky;
            ar[pos][i].len=ar[pos][i].c+l;
            ar[pos][i].val=0;
            continue;
        }
        ar[pos][i].x=ar[kx][ky].x;
        ar[pos][i].y=ar[kx][ky].y;
        ar[pos][i].len=ar[kx][ky].len;
        ar[pos][i].val=ar[kx][ky].val+1;
    }
}
void insert1(int x)
{
    int i,j,*e,pos,b,kx,ky,sx,sy,slen;
    e=upper_bound(d+1,d+p+1,x);
    pos=e-d-1;
    if(pos==0) pos=1, d[1]=x;
    for(i=1;i<=leng[pos];i++){
        if(ar[pos][i].c>x || ar[pos][i].x==0) break;
    }
    b=i;
    sx=ar[pos][b].x; sy=ar[pos][b].y; slen=ar[pos][b].len;
    for(i=leng[pos]+1;i>=b+1;i--){
        ar[pos][i].c=ar[pos][i-1].c; ar[pos][i].x=ar[pos][i-1].x; ar[pos][i].y=ar[pos][i-1].y; ar[pos][i].len=ar[pos][i-1].len; ar[pos][i].val=ar[pos][i-1].val;
    }
    ar[pos][b].c=x;
    if(b==1) d[pos]=ar[pos][b].c;
    leng[pos]++;
    if(b==leng[pos]) sx=pos+1, sy=1, slen=ar[pos][b].c+l;
    balance(sx,sy,slen);
    kx=ix; ky=iy;
    for(i=b;i>=1;i--){
        while(ar[kx][ky].c-ar[pos][i].c>l){
            ky--;
            if(ky==0){kx--; ky=leng[kx];}
            if(ar[kx][ky].c==0){ kx--; ky=leng[kx];}
        }
        ky++;
        if(ky==leng[kx]+1){kx++; ky=1;}
        if(kx==p+1){
            ar[pos][i].x=kx;
            ar[pos][i].y=1;
            ar[pos][i].len=ar[pos][i].c+l;
            ar[pos][i].val=0;
            continue;
        }
        if(kx>pos){
            ar[pos][i].x=kx;
            ar[pos][i].y=ky;
            ar[pos][i].len=ar[pos][i].c+l;
            ar[pos][i].val=0;
            continue;
        }
        ar[pos][i].x=ar[kx][ky].x;
        ar[pos][i].y=ar[kx][ky].y;
        ar[pos][i].len=ar[kx][ky].len;
        ar[pos][i].val=ar[kx][ky].val+1;
    }
}
void query()
{
    int kx,ky,i,j,sx,sy,slen;
    for(i=1;;i++){
        if(leng[i]!=0) break;
    }
    kx=i; ky=1;
    while(1){
        if(kx==p-1) kx=p-1;
        sx=ar[kx][ky].x; sy=ar[kx][ky].y; slen=ar[kx][ky].len; dap+=ar[kx][ky].val+1;
        if(sy>leng[sx]) sy=leng[sx];
        if(sy==0){sx--; sy=leng[sx];}
        balance(sx,sy,slen);
        kx=ix; ky=iy;
        if(kx==p+1) break;
    }
}
void reset()
{
    int i,j,kx,ky;
    r=1;
    for(i=1;i<=n;i++){
        for(j=r;j<=n;j++){
            if(a[j]-a[i]>l) break;
        }
        r=j;
        if(q==k) p++, q=0;
        q++;
        if(r==n+1){
            ar[p][q].x=n/k+1;
            if(n%k!=0) ar[p][q].x++;
            ar[p][q].y=1;
            ar[p][q].c=a[i];
            leng[p]++;
            r--;
            continue;
        }
        ar[p][q].x=(r-1)/k+1;
        ar[p][q].y=r%k; if(ar[p][q].y==0) ar[p][q].y=k;
        ar[p][q].c=a[i];
        leng[p]++;
        r--;
    }
    for(i=p;i>=1;i--){
        for(j=leng[i];j>=1;j--){
            if(i==ar[i][j].x){
                kx=ar[i][j].x; ky=ar[i][j].y;
                if(ar[kx][ky].x==0){ar[i][j].len=ar[i][j].c+l; continue;}
                ar[i][j].x=ar[kx][ky].x; ar[i][j].y=ar[kx][ky].y; ar[i][j].val=ar[kx][ky].val+1; ar[i][j].len=ar[kx][ky].len;
            }
            else{
                ar[i][j].len=ar[i][j].c+l;
            }
        }
        d[i]=ar[i][1].c;
    }
    ar[p+1][1].c=2147483647;
}
void init(int N, int L, int X[])
{
    int i,j,kx=1,ky=0,w;
    n = N;
    l=L;
    for(i=1; i<=N; i++)
    {
        a[i]=X[i-1];
        a[i]++;
        a2[i]=a[i];
    }
    k=sqrt(n);
    if(k*k<n) k++;
    reset();
}

int update(int s, int t)
{
    int i=0,j,kx=1,ky=0,w;
    s++;
    t++; i++;
    erase1(a2[s]);
    insert1(t);
    dap=0;
    query();
    a2[s]=t;
    if(i%k==0)
    {
        kx=1, ky=0, w=0;
        while(1)
        {
            while(ky==leng[kx]) kx++, ky=0;
            ky++;
            if(kx>=p+1) break;
            a[++w]=ar[kx][ky].c;
        }
        memset(leng,0,sizeof leng);
        memset(ar,0,sizeof ar);
        p=1, q=0;
        reset();
    }
    return dap;
}

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 25316 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 25316 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 25316 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 25316 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 92 ms 25316 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -