Submission #943870

#	Time	Username	Problem	Language	Result	Execution time	Memory
943870		sleepntsheep	Dancing Elephants (IOI11_elephants)	C11	26 / 100	17 ms	13404 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 400
#define NS 900

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

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*)malloc(2*sizeof**aa),dp[i]=(A*)malloc(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)
{
    if(!ao[i])return;
    dp[i][ao[i]-1] = (A){1,x[aa[i][ao[i]-1]] + l};
    for(int j=ao[i]-2,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);
}

void init(int n_, int l_, int x_[])
{
    x=x_;
    n=n_,l=l_;
    for(int i=0;i<n;++i)ins(i/S,i%S,i);

    getans();
}

int update(int j, int y)
{
    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;
    }

    if(!~np)while(puts("@")+1);

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

    return getans();
}

Compilation message (stderr)

elephants.c: In function 'push':
elephants.c:28:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   28 |     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: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3