oj.uz

Submission #940635

# Submission time Handle Problem Language Result Execution time Memory
940635 2024-03-07T12:19:36 Z sleepntsheep Fountain (eJOI20_fountain) C
100 / 100
 129 ms 20832 KB 
#include<stdio.h>
#include<stdlib.h>
#define N 100000
#define N_ 100001
int n,q,d[N],c[N],ss[N],so,ng[N],*eh[N_],eo[N_],dd[N_],jj[N_],pp[N_];
long long cc[N_];

void append(int i,int j)
{
    int o=eo[i]++;
    if(o>=2&&(o&o-1)==0)eh[i]=(int*)realloc(eh[i],sizeof**eh*2*o);
    eh[i][o]=j;
}

void dfs(int u,int p)
{
    for(int j=0;j<eo[u];++j)
    {
        dd[eh[u][j]]=dd[u]+1;
        jj[eh[u][j]] = (dd[u]-dd[jj[u]]==dd[jj[u]]-dd[jj[jj[u]]])?jj[jj[u]]:u;
        pp[eh[u][j]]=u;
        cc[eh[u][j]]=cc[u]+c[eh[u][j]];
        dfs(eh[u][j],u);
    }
}

int lift(int u,long long x)
{
    long long ccu = cc[u];
    while (u != n && x - (ccu - cc[u]) > c[u])
        u = (x - (ccu - cc[jj[u]]) > c[jj[u]]) ? jj[u] : pp[u];
    return u;
}

int main()
{
    scanf("%d%d",&n,&q);
    for(int i=0;i<n;++i)scanf("%d%d",d+i,c+i);
    for(int i=0;i<n;ss[so++]=i++)while(so&&d[ss[so-1]]<d[i])ng[ss[--so]]=i;
    while(so)ng[ss[--so]]=n;
    for(int i=0;i<=n;++i)eh[i]=(int*)malloc(2*sizeof**eh);
    for(int i=0;i<n;++i)append(ng[i],i);
    pp[n]=jj[n]=n;
    dfs(n,n);
    for(int u,x;q--;)
    {
        scanf("%d%d",&u,&x);
        --u;
        u=lift(u,x);
        printf("%d\n",u==n?0:u+1);
    }
}

Compilation message

fountain.c: In function 'append':
fountain.c:11:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   11 |     if(o>=2&&(o&o-1)==0)eh[i]=(int*)realloc(eh[i],sizeof**eh*2*o);
      |                 ~^~
fountain.c: In function 'main':
fountain.c:37:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     scanf("%d%d",&n,&q);
      |     ^~~~~~~~~~~~~~~~~~~
fountain.c:38:25: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     for(int i=0;i<n;++i)scanf("%d%d",d+i,c+i);
      |                         ^~~~~~~~~~~~~~~~~~~~~
fountain.c:47:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |         scanf("%d%d",&u,&x);
      |         ^~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 18520 KB Output is correct
2 Correct 104 ms 17888 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 2 ms 2652 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 2 ms 2396 KB Output is correct
8 Correct 89 ms 18520 KB Output is correct
9 Correct 104 ms 17888 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 49 ms 8504 KB Output is correct
12 Correct 129 ms 20832 KB Output is correct
13 Correct 115 ms 14212 KB Output is correct
14 Correct 83 ms 11856 KB Output is correct
15 Correct 78 ms 12880 KB Output is correct