oj.uz

Submission #943877

# Submission time Handle Problem Language Result Execution time Memory
943877 2024-03-12T03:25:20 Z sleepntsheep Dancing Elephants (IOI11_elephants) C
50 / 100
 9000 ms 12556 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,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],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,bb[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);
}


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: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 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 2 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 2 ms 8540 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 8540 KB Output is correct
7 Correct 1381 ms 9084 KB Output is correct
8 Correct 1932 ms 9160 KB Output is correct
9 Correct 4014 ms 9992 KB Output is correct
10 Correct 4477 ms 10068 KB Output is correct
11 Correct 4046 ms 11280 KB Output is correct
12 Correct 5637 ms 11452 KB Output is correct
13 Correct 4416 ms 11132 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 8540 KB Output is correct
7 Correct 1381 ms 9084 KB Output is correct
8 Correct 1932 ms 9160 KB Output is correct
9 Correct 4014 ms 9992 KB Output is correct
10 Correct 4477 ms 10068 KB Output is correct
11 Correct 4046 ms 11280 KB Output is correct
12 Correct 5637 ms 11452 KB Output is correct
13 Correct 4416 ms 11132 KB Output is correct
14 Correct 2390 ms 10944 KB Output is correct
15 Correct 3471 ms 10692 KB Output is correct
16 Correct 8406 ms 11856 KB Output is correct
17 Execution timed out 9031 ms 12556 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 2 ms 8540 KB Output is correct
7 Correct 1381 ms 9084 KB Output is correct
8 Correct 1932 ms 9160 KB Output is correct
9 Correct 4014 ms 9992 KB Output is correct
10 Correct 4477 ms 10068 KB Output is correct
11 Correct 4046 ms 11280 KB Output is correct
12 Correct 5637 ms 11452 KB Output is correct
13 Correct 4416 ms 11132 KB Output is correct
14 Correct 2390 ms 10944 KB Output is correct
15 Correct 3471 ms 10692 KB Output is correct
16 Correct 8406 ms 11856 KB Output is correct
17 Execution timed out 9031 ms 12556 KB Time limit exceeded
18 Halted 0 ms 0 KB -