Cod sursa(job #633033)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 12 noiembrie 2011 19:55:04
Problema Tribute Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#define N 50002
long x[N],y[N],n,dx,dy,i,a[N],b[N];

void merge(long x[N],long y[N],long p,long q)
{long i,j,k,m=(p+q)/2;
if(p==q)
      return;
merge(x,y,p,m);
merge(x,y,m+1,q);
for(i=k=p,j=m+1;i<=m||j<=q;)
if(j>q||(i<=m&&(x[i]<x[j]||(x[i]==x[j]&&y[i]<y[j]))))
      a[k]=x[i],b[k++]=y[i++];
else
      a[k]=x[j],b[k++]=y[j++];
for(i=p;i<=q;i++)
      x[i]=a[i],y[i]=b[i];}
      
long h(long x[N],long y[N],long n,long dx,long dy)
{long i,m=N,s[N],z[N],p[N],r[N];
merge(x,y,1,n);
for(i=x[1];i<=x[n];i++)
      s[i]=z[i]=p[i]=r[i]=0;
for(i=1;i<=n;i++)
      z[x[i]]++,s[x[i]]++;
z[x[1]-1]=p[x[1]-1]=s[x[n]-x[1]+2]=r[x[1]-1]=0;
for(i=x[1];i<=x[n]-dx;i++)
      {z[i-1]+=z[i-2];
      p[i]=p[i-1]+z[i-1];
      s[x[n]-i+1]+=s[x[n]-i+2];
      r[i]=r[i-1]+s[x[n]-i+1];}
for(i=x[1];i<=x[n]-dx;i++)
if(m>p[i]+r[x[n]-dx-i])
      m=p[i]+r[x[n]-dx-i];
return m;}

int main()
{FILE *f=fopen("tribute.in","r"),*g=fopen("tribute.out","w");
fscanf(f,"%ld%ld%ld",&n,&dx,&dy);
for(i=1;i<=n;i++)
      fscanf(f,"%ld%ld",&x[i],&y[i]);
fprintf(g,"%ld",h(x,y,n,dx,dy)+h(y,x,n,dy,dx));
return 0;}