Submission #973028

#	Time	Username	Problem	Language	Result	Execution time	Memory
973028		sleepntsheep	Palembang Bridges (APIO15_bridge)	C11	22 / 100	53 ms	5208 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 cmpr(const void*a,const void*b){return *(const int*)a - *(const int*)b;}

int n, k, c[1+(MAX_N<<1)], p, 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)-(s[j]+t[j]);return dir<0?-1:dir>0?1:0;}
long long cost, z = 1e18;

#define MM 400000
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;
        while(losz<hisz)
            hisum-=ha[hi],losum+=ha[hi],lo=hinsert(lo,ha[hi],lt),hi=hpop(hi,gt),--hisz,++losz;
    }
    else
    {
        lo=hinsert(lo,x,lt);
        ++losz,losum+=x;
        while(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,c[++p] = ss, c[++p] = tt,++cost;
    }

    if(o<2)k=1;

    if(k==1)
    {
        qsort(c+1, p, sizeof*c, cmpr);
        for(int j=1;j<=p;++j) cost += abs(c[p/2] - c[j]);
        printf("%lld\n", cost);
        return 0;
    }

    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;

    hi=lo=halc=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:60:49: warning: operation on 'o' may be undefined [-Wsequence-point]
   60 |         else s[o]=min(ss,tt),t[o]=max(ss,tt),e[o++]=o,c[++p] = ss, c[++p] = tt,++cost;
      |                                                ~^~
bridge.c:54:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |     scanf("%d%d", &k, &n);
      |     ^~~~~~~~~~~~~~~~~~~~~
bridge.c:58:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         scanf(" %c%d %c%d",&bb,&ss,&cc,&tt);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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