Codeforces Round #386 (Div. 2), problem: (F) Music in Car Solution in C/C++

Codeforces Round #386 (Div. 2), problem: (F) Music in Car Solution in C/C++

#include <stdio.h>
#include <string.h>
#define MAX(X,Y) ((X)>(Y) ? (X) : (Y))

int n,w,k,a[200010],t[200010],sz[2],heap[2][200010],ind[200010],pos[200010];
void push(int k,int opt);
int pop(int opt);
void del(int u,int opt);
void up(int u,int opt);
void down(int u,int opt);
int cmp(int u,int v,int opt);
void swap(int u,int v,int opt);

int main(void)
{
    //freopen("music.in","r",stdin);
    //freopen("music.out","w",stdout);
    scanf("%d%d%d",&n,&w,&k);
    int i;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&t[i]);
    sz[0]=sz[1]=0;
    memset(pos,-1,sizeof(pos));
    int l=1,s=0,st=0,ans=0,p;
    for(sz[0]=sz[1]=0,i=1;i<=n;i++)
    {
        push(i,0);
        s+=a[i];  st+=(t[i]+1)/2;
        if(sz[0]>w)
        {
            p=pop(0);
            st-=(t[p]+1)/2;
            push(p,1);
            st+=t[p];
        }
        while(st>k)
        {
            if(pos[l])
            {
                del(ind[l],1);
                s-=a[l];  st-=t[l];
            }
            else
            {
                del(ind[l],0);
                s-=a[l];  st-=(t[l]+1)/2;
                if(sz[1])
                {
                    p=pop(1);
                    st-=t[p];
                    push(p,0);
                    st+=(t[p]+1)/2;
                }
            }
            l++;
        }
        ans=MAX(ans,s);
    }
    printf("%d\n",ans);
    return 0;
}

void push(int k,int opt)
{
    heap[opt][++sz[opt]]=k;
    pos[k]=opt;  ind[k]=sz[opt];
    up(sz[opt],opt);
}

int pop(int opt)
{
    int ans=heap[opt][1];
    swap(1,sz[opt],opt);
    sz[opt]--;
    down(1,opt);
    return ans;
}

void del(int u,int opt)
{
    swap(u,sz[opt],opt);
    sz[opt]--;
    if( u>1 && cmp(u,u/2,opt)<0 ) up(u,opt);
    else down(u,opt);
}

void up(int u,int opt)
{
    if( u>1 && cmp(u,u/2,opt)<0 )
    {
        swap(u,u/2,opt);
        up(u/2,opt);
    }
}

void down(int u,int opt)
{
    if(u*2>sz[opt]) return;
    int v=u*2;
    if( v+1<=sz[opt] && cmp(v+1,v,opt)<0 ) v++;
    if(cmp(v,u,opt)<0)
    {
        swap(u,v,opt);
        down(v,opt);
    }
}

int cmp(int u,int v,int opt)
{
    int ans;
    if(t[heap[opt][u]]<t[heap[opt][v]]) ans=-1;
    else if(t[heap[opt][u]]>t[heap[opt][v]]) ans=1;
    else ans=0;
    if(opt) ans*=-1;
    return ans;
}

void swap(int u,int v,int opt)
{
    int t1,t2;
    t1=heap[opt][u];  t2=heap[opt][v];
    heap[opt][u]=t2;  heap[opt][v]=t1;
    ind[t2]=u;  ind[t1]=v;
}

Codeforces Round #386 (Div. 2), problem: (F) Music in Car Solution in C/C++

#include <stdio.h>
#include <string.h>
#define MAX(X,Y) ((X)>(Y) ? (X) : (Y))

int n,w,k,a[200010],t[200010],sz[2],heap[2][200010],ind[200010],pos[200010];
void push(int k,int opt);
int pop(int opt);
void del(int u,int opt);
void up(int u,int opt);
void down(int u,int opt);
int cmp(int u,int v,int opt);
void swap(int u,int v,int opt);

int main(void)
{
    //freopen("music.in","r",stdin);
    //freopen("music.out","w",stdout);
    scanf("%d%d%d",&n,&w,&k);
    int i;
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&t[i]);
    sz[0]=sz[1]=0;
    memset(pos,-1,sizeof(pos));
    int l=1,s=0,st=0,ans=0,p;
    for(sz[0]=sz[1]=0,i=1;i<=n;i++)
    {
        push(i,0);
        s+=a[i];  st+=(t[i]+1)/2;
        if(sz[0]>w)
        {
            p=pop(0);
            st-=(t[p]+1)/2;
            push(p,1);
            st+=t[p];
        }
        while(st>k)
        {
            if(pos[l])
            {
                del(ind[l],1);
                s-=a[l];  st-=t[l];
            }
            else
            {
                del(ind[l],0);
                s-=a[l];  st-=(t[l]+1)/2;
                if(sz[1])
                {
                    p=pop(1);
                    st-=t[p];
                    push(p,0);
                    st+=(t[p]+1)/2;
                }
            }
            l++;
        }
        ans=MAX(ans,s);
    }
    printf("%d\n",ans);
    return 0;
}

void push(int k,int opt)
{
    heap[opt][++sz[opt]]=k;
    pos[k]=opt;  ind[k]=sz[opt];
    up(sz[opt],opt);
}

int pop(int opt)
{
    int ans=heap[opt][1];
    swap(1,sz[opt],opt);
    sz[opt]--;
    down(1,opt);
    return ans;
}

void del(int u,int opt)
{
    swap(u,sz[opt],opt);
    sz[opt]--;
    if( u>1 && cmp(u,u/2,opt)<0 ) up(u,opt);
    else down(u,opt);
}

void up(int u,int opt)
{
    if( u>1 && cmp(u,u/2,opt)<0 )
    {
        swap(u,u/2,opt);
        up(u/2,opt);
    }
}

void down(int u,int opt)
{
    if(u*2>sz[opt]) return;
    int v=u*2;
    if( v+1<=sz[opt] && cmp(v+1,v,opt)<0 ) v++;
    if(cmp(v,u,opt)<0)
    {
        swap(u,v,opt);
        down(v,opt);
    }
}

int cmp(int u,int v,int opt)
{
    int ans;
    if(t[heap[opt][u]]<t[heap[opt][v]]) ans=-1;
    else if(t[heap[opt][u]]>t[heap[opt][v]]) ans=1;
    else ans=0;
    if(opt) ans*=-1;
    return ans;
}

void swap(int u,int v,int opt)
{
    int t1,t2;
    t1=heap[opt][u];  t2=heap[opt][v];
    heap[opt][u]=t2;  heap[opt][v]=t1;
    ind[t2]=u;  ind[t1]=v;
}