Submission #973039

#	Time	Username	Problem	Language	Result	Execution time	Memory
973039		sleepntsheep	Palembang Bridges (APIO15_bridge)	C11	63 / 100	246 ms	262144 KiB

bridge

#include <stdio.h>
#include <stdlib.h>
#define MAX_N 100000

int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}

int n, k, s[MAX_N], t[MAX_N], e[MAX_N], o, temp;long long pref[MAX_N];
int cmpr2(const void*a,const void*b){int i=*(const int*)a,j=*(const int*)b;long long dir=(s[i]+t[i]+0ll)-(0ll+s[j]+t[j]);return dir<0?-1:dir>0?1:0;}
long long cost, z = 1e18;

#define MM 400003
int ha[MM],hl[MM],hr[MM],halc=0;char hs[MM];
int lt(int a,int b){return a<b;}
int gt(int a,int b){return a>b;}
int hmerge(int l,int r,int(*lt)(int,int))
{
    if(!l||!r)return l^r;
    if(lt(ha[l],ha[r]))return hmerge(r,l,lt);
    hr[l]=hmerge(hr[l],r,lt);
    if(hs[hr[l]]>hs[hl[l]])temp=hr[l],hr[l]=hl[l],hl[l]=temp;
    hs[l]=hs[hr[l]]+1;
    return l;
}
int hpop(int v,int(*lt)(int,int)) { return hmerge(hl[v],hr[v], lt); }
int hnode(int k){int p=++halc;hs[p]=1;hl[p]=hr[p]=0;ha[p]=k;return p;}
int hinsert(int v,int k,int(*lt)(int,int)){return hmerge(v,hnode(k),lt);}

/* sliding median */
int lo, hi, losz, hisz;
long long losum,hisum;

void ins(int x)
{
    if(losz>0&&ha[lo]<x)
        hi=hinsert(hi,x,gt), ++hisz,hisum+=x;
    else
        lo=hinsert(lo,x,lt), ++losz,losum+=x;
    if(losz<hisz)
        hisum-=ha[hi],losum+=ha[hi],lo=hinsert(lo,ha[hi],lt),hi=hpop(hi,gt),--hisz,++losz;
    else if(hisz+1<losz)
        losum-=ha[lo],hisum+=ha[lo],hi=hinsert(hi,ha[lo],gt),lo=hpop(lo,lt),--losz,++hisz;
}

int main()
{
    scanf("%d%d", &k, &n);
    for (int ss, tt, i = 0; i < n; ++i)
    {
        char bb, cc;
        scanf(" %c%d %c%d",&bb,&ss,&cc,&tt);
        if(bb==cc) cost += abs(tt-ss);
        else s[o]=min(ss,tt),t[o]=max(ss,tt),e[o]=o,++cost,++o;
    }

    qsort(e,o,sizeof*e,cmpr2);

    for(int i=0;i<o;++i)
        ins(s[e[i]]),ins(t[e[i]]), pref[i] = hisum-losum;
    if(k==1){printf("%lld\n",hisum-losum+cost);return 0;}

    hi=lo=hisz=losz=hisum=losum=0;
    for(int i=o-1;i>=1;--i)
    {
        ins(s[e[i]]),ins(t[e[i]]);
        if(hisum-losum+pref[i-1]<z)z=hisum-losum+pref[i-1];
    }
    if(pref[o-1]<z)z=pref[o-1];

    printf("%lld",z+cost);
}

Compilation message (stderr)

bridge.c: In function 'main':
bridge.c:47:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |     scanf("%d%d", &k, &n);
      |     ^~~~~~~~~~~~~~~~~~~~~
bridge.c:51:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf(" %c%d %c%d",&bb,&ss,&cc,&tt);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 32 / 32
• Subtask 5: 0 / 37