oj.uz

Submission #943878

# Submission time Handle Problem Language Result Execution time Memory
943878 2024-03-12T03:27:23 Z sleepntsheep Dancing Elephants (IOI11_elephants) C
100 / 100
 3502 ms 18296 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 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()
{
    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;
    }

    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

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 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 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct

Subtask #3
24.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 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 193 ms 9084 KB Output is correct
8 Correct 226 ms 9052 KB Output is correct
9 Correct 281 ms 9816 KB Output is correct
10 Correct 305 ms 10000 KB Output is correct
11 Correct 287 ms 10004 KB Output is correct
12 Correct 517 ms 10012 KB Output is correct
13 Correct 308 ms 9820 KB Output is correct

Subtask #4
47.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 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 193 ms 9084 KB Output is correct
8 Correct 226 ms 9052 KB Output is correct
9 Correct 281 ms 9816 KB Output is correct
10 Correct 305 ms 10000 KB Output is correct
11 Correct 287 ms 10004 KB Output is correct
12 Correct 517 ms 10012 KB Output is correct
13 Correct 308 ms 9820 KB Output is correct
14 Correct 310 ms 9316 KB Output is correct
15 Correct 369 ms 9052 KB Output is correct
16 Correct 861 ms 9992 KB Output is correct
17 Correct 943 ms 10524 KB Output is correct
18 Correct 986 ms 12508 KB Output is correct
19 Correct 480 ms 12704 KB Output is correct
20 Correct 935 ms 12580 KB Output is correct
21 Correct 889 ms 12380 KB Output is correct
22 Correct 499 ms 12124 KB Output is correct

Subtask #5
3.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 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 193 ms 9084 KB Output is correct
8 Correct 226 ms 9052 KB Output is correct
9 Correct 281 ms 9816 KB Output is correct
10 Correct 305 ms 10000 KB Output is correct
11 Correct 287 ms 10004 KB Output is correct
12 Correct 517 ms 10012 KB Output is correct
13 Correct 308 ms 9820 KB Output is correct
14 Correct 310 ms 9316 KB Output is correct
15 Correct 369 ms 9052 KB Output is correct
16 Correct 861 ms 9992 KB Output is correct
17 Correct 943 ms 10524 KB Output is correct
18 Correct 986 ms 12508 KB Output is correct
19 Correct 480 ms 12704 KB Output is correct
20 Correct 935 ms 12580 KB Output is correct
21 Correct 889 ms 12380 KB Output is correct
22 Correct 499 ms 12124 KB Output is correct
23 Correct 2419 ms 17076 KB Output is correct
24 Correct 2519 ms 17160 KB Output is correct
25 Correct 1851 ms 16920 KB Output is correct
26 Correct 2333 ms 17084 KB Output is correct
27 Correct 2082 ms 16724 KB Output is correct
28 Correct 858 ms 11864 KB Output is correct
29 Correct 889 ms 11736 KB Output is correct
30 Correct 874 ms 11716 KB Output is correct
31 Correct 846 ms 11856 KB Output is correct
32 Correct 1878 ms 16720 KB Output is correct
33 Correct 1875 ms 15828 KB Output is correct
34 Correct 2065 ms 16712 KB Output is correct
35 Correct 1916 ms 17564 KB Output is correct
36 Correct 2232 ms 16720 KB Output is correct
37 Correct 2745 ms 18296 KB Output is correct
38 Correct 1914 ms 15696 KB Output is correct
39 Correct 1835 ms 16752 KB Output is correct
40 Correct 2041 ms 15740 KB Output is correct
41 Correct 3357 ms 16512 KB Output is correct
42 Correct 3502 ms 16844 KB Output is correct