Submission #940635

#	Time	Username	Problem	Language	Result	Execution time	Memory
940635		sleepntsheep	Fountain (eJOI20_fountain)	C11	100 / 100	129 ms	20832 KiB

fountain

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40