Cod sursa(job #123119)

Utilizator alexeiIacob Radu alexei Data 14 ianuarie 2008 18:27:35
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
#include<stdio.h>
#define nmax 50000
#define inf 2147483647
            
char q[nmax],w[nmax];
long long a[nmax],b[nmax];
long long mint=inf,max=inf;
int main()
{
 freopen("tribute.in","r",stdin);
 freopen("tribute.out","w",stdout);
 
 int n,val1,val2,pl1,pl2;
 scanf("%d%d%d",&n,&pl1,&pl2);
    int i,sum,min;
    for(i=1; i<=n; i++)
   { scanf("%d %d",&val1,&val2);
     q[val1]='1';
     w[val2]='1';
     }
    
    sum=0; 
    for(i=0; i<=nmax; ++i)
{   a[i]=a[i-1]+sum;
      if(q[i]=='1')
      ++sum;
}
    sum=0;
    for(i=nmax; i>=0; --i)
{   b[i]=b[i+1]+sum;
      if(q[i]=='1')
      ++sum;
} 
    
    for(i=0; i<=nmax; ++i)
{   min=a[i]+b[i];
    if(min<mint)
    mint=min;
}
  
    sum=0; 
    for(i=0; i<=nmax; ++i)
{   a[i]=a[i-1]+sum;
      if(w[i]=='1')
      ++sum;
}
    sum=0;
    for(i=nmax; i>=0; --i)
{   b[i]=b[i+1]+sum;
      if(w[i]=='1')
      ++sum;
} 
    
    for(i=0; i<=nmax; ++i)
{   min=a[i]+b[i];
    if(min<max)
    max=min;
    
}
    --pl1;
    --pl2;
 printf("%lld\n",mint+max-pl1-pl2);   
    
    
    
    
    return 0;
}