oj.uz

Submission #943873

# Submission time Handle Problem Language Result Execution time Memory
943873 2024-03-12T03:16:56 Z sleepntsheep Dancing Elephants (IOI11_elephants) C
26 / 100
 4065 ms 105780 KB 
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[N][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);
}

int count = 0,bb[N],bo;

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

    for(int i=0;i<n;++i)ins(i/S,i%S,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)
{
    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

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

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1290 ms 33332 KB Output is correct
8 Correct 1752 ms 42704 KB Output is correct
9 Correct 4065 ms 105780 KB Output is correct
10 Incorrect 89 ms 12136 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1290 ms 33332 KB Output is correct
8 Correct 1752 ms 42704 KB Output is correct
9 Correct 4065 ms 105780 KB Output is correct
10 Incorrect 89 ms 12136 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 1290 ms 33332 KB Output is correct
8 Correct 1752 ms 42704 KB Output is correct
9 Correct 4065 ms 105780 KB Output is correct
10 Incorrect 89 ms 12136 KB Output isn't correct
11 Halted 0 ms 0 KB -