oj.uz

Submission #943866

# Submission time Handle Problem Language Result Execution time Memory
943866 2024-03-12T03:06:20 Z sleepntsheep Dancing Elephants (IOI11_elephants) C
26 / 100
 16 ms 13400 KB 
int hi(int a,int b){return a>b?a:b;}
#include "elephants.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)
{
    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);

    //for(int i=0;i<n;++i) printf(" : %d %d %d\n",i,dp[0][i].a,dp[0][i].b);
    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(x[aa[i][ao[i]-1]] >= y)
            nb=i;
    if(!~nb)nb=(n-1)/S;

    for(int k=0;!~np&&k<ao[nb];++k)
    {
        //printf(" Checking NEW %d %d %d (%d)\n",k,x[aa[nb][k]],y,ao[nb]);
        if(x[aa[nb][k]]>=y) np=k;
    }
    if(!~np)np=ao[nb];

    //printf(" Removing %d from (%d %d) and inserting at (%d %d)\n",j,at[j][0],at[j][1],nb,np);
    //for(int i=0;i<n;++i) printf(" : %d (x %d) ",aa[0][i],x[aa[0][i]]);puts("");
    x[j]=y;

    ins(nb,np,j);

    //for(int i=0;i<n;++i) printf(" : %d (x %d) ",aa[0][i],x[aa[0][i]]);puts("");

    return getans();
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Runtime error 16 ms 13400 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Runtime error 16 ms 13400 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Runtime error 16 ms 13400 KB Execution killed with signal 6
8 Halted 0 ms 0 KB -