Submission #943881

#	Time	Username	Problem	Language	Result	Execution time	Memory
943881		sleepntsheep	Dancing Elephants (IOI11_elephants)	C11	100 / 100	3759 ms	13304 KiB

elephants

int hi(int a,int b){return a>b?a:b;}
#include "elephants.h"
#include<assert.h>
#include<stdio.h>
#include<stdlib.h>

#define N 150005
#define S 300
#define NS 550

int n,l,*x,at[N][2];
int *aa[NS],ao[NS];

typedef struct { int a,b; } A;
A *dp[NS];

A merge(A a,A b)
{
    if (a.a==b.a)return a.b>b.b?a:b;
    return a.a<b.a?a:b;
}

void push(int i,int j)
{
    int o=ao[i]++;
    if(!o)aa[i]=(int*)realloc(aa[i],2*sizeof**aa),dp[i]=(A*)realloc(dp[i],sizeof**dp*2);
    else if(o>=2&&(o&o-1)==0)aa[i]=(int*)realloc(aa[i],2*o*sizeof**aa),dp[i]=(A*)realloc(dp[i],2*o*sizeof**dp);
    aa[i][o]=j;
}

void dpize(int i)
{
    for(int j=ao[i]-1,k=ao[i]-1;j>=0;--j)
    {
        while(x[aa[i][k]]-x[aa[i][j]]>l)--k;
        if(k+1==ao[i]) dp[i][j]=(A){1,x[aa[i][j]] + l};
        else dp[i][j]=(A){dp[i][k+1].a+1,dp[i][k+1].b};
    }
    for(int j=0;j<ao[i];++j) at[aa[i][j]][0]=i,at[aa[i][j]][1]=j;
}

int getans()
{
    int z=0,j=-1;
    for(int i=0;i*S<n;++i)
    {
        int zz=-1,ll=0,rr=ao[i]-1;
        while(ll<=rr)
        {
            int mm=(ll+rr)/2;
            if(x[aa[i][mm]]>j)zz=mm,rr=mm-1;
            else ll=mm+1;
        }
        if(~zz) {
            z+=dp[i][zz].a;
            j=dp[i][zz].b;
        }
    }
    return z;
}

void del(int i,int j)
{
    for(int l=j;l+1<ao[i];++l)aa[i][l]=aa[i][l+1];
    --ao[i];
    dpize(i);
}

void ins(int i,int j,int k)
{
    push(i,0);
    for(int l=ao[i]-1;l>j;--l)aa[i][l]=aa[i][l-1];
    aa[i][j]=k;
    dpize(i);
}

int count=0,bb[N];

void build()
{
    for(int i=0;i<n;++i) push(i/S,bb[i]);
    for(int i=0;i*S<n;++i)dpize(i);
}

void rebuild()
{
    for(int bo=0,i=0;i*S<n;ao[i++]=0)
        for(int j=0;j<ao[i];++j)
            bb[bo++]=aa[i][j];

    build();
}

void init(int n_, int l_, int x_[])
{
    x=x_;
    n=n_,l=l_;
    for(int i=0;i<n;++i)bb[i]=i;
    build();
}

int update(int j, int y)
{
    if(++count % S == 0) rebuild();

    del(at[j][0],at[j][1]);
    int nb=-1,np=-1;
    for(int i=0;!~nb&&i*S<n;++i)
        if(ao[i]>0&&x[aa[i][ao[i]-1]] >= y)
            nb=i;
    if(!~nb)nb=(n-1)/S,np=ao[(n-1)/S];

    for(int k=0;!~np&&k<ao[nb];++k)
        if(x[aa[nb][k]]>=y) np=k;

    x[j]=y;
    ins(nb,np,j);

    return getans();
}

Compilation message (stderr)

elephants.c: In function 'push':
elephants.c:27:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   27 |     else if(o>=2&&(o&o-1)==0)aa[i]=(int*)realloc(aa[i],2*o*sizeof**aa),dp[i]=(A*)realloc(dp[i],2*o*sizeof**dp);
      |                      ~^~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 3 / 3