Cod sursa(job #137381)

Utilizator savimSerban Andrei Stan savim Data 17 februarie 2008 11:52:11
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasele 5-8 Marime 2.18 kb
#include <stdio.h>
#define l 100010
int i,j,k,n,m;
long long sum=0;
int a[l][2],b[l][2],poz[l];
void inter(int p, int q)
{
	 int r=(p+q)/2,x,y,k=0;
	 x=p;y=r+1;
     while (x<=r && y<=q)
     {
         k++;
         if (a[x][1]<a[y][1]) {b[k][0]=a[x][0];b[k][1]=a[x][1];x++;}
         else {b[k][0]=a[y][0];b[k][1]=a[y][1];y++;}
     }
     while (x<=r) {k++;b[k][0]=a[x][0];b[k][1]=a[x][1];x++;}
     while (y<=q) {k++;b[k][0]=a[y][0];b[k][1]=a[y][1];y++;}     
     k=0;
     for (i=p; i<=q; i++) { k++;a[i][0]=b[k][0];a[i][1]=b[k][1];}    
}
void inter2(int p, int q)
{
     int r=(p+q)/2,x,y,k=0;
     x=p;y=r+1;
     while (x<=r && y<=q)
     {
         k++;
		 if (a[x][0]<a[y][0]) {b[k][0]=a[x][0];b[k][1]=a[x][1];x++;}
		 else {b[k][0]=a[y][0];b[k][1]=a[y][1];y++;}
     }
     while (x<=r) {k++;b[k][0]=a[x][0];b[k][1]=a[x][1];x++;}
     while (y<=q) {k++;b[k][0]=a[y][0];b[k][1]=a[y][1];y++;}     
     k=0;
     for (i=p; i<=q; i++) { k++;a[i][0]=b[k][0];a[i][1]=b[k][1];}    
}
void merge(int p, int q, int k)
{
     int r=(p+q)/2;
	 if (p==q) return;
     merge(p,r,k);
     merge(r+1,q,k);
	 if (k==0) inter(p,q);
	 else inter2(p,q);
	 if (p>=q) return;
}
int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
    
    scanf("%d",&n);
    for (i=1; i<=n; i++)
		scanf("%d %d",&a[i][0],&a[i][1]);
    
    merge(1,n,0);
    i=0;
	while (i<n)
    {
        i++;
		if (i==n+1) break;
		k=i;
		while (a[i][1]==a[i+1][1] && i<n) i++;
		if (i>k) i--;
        if (i!=k) merge(k,i,1);
    }
    
    m=1;poz[1]=1;
    for (i=2; i<=n; i++)
	if (a[i][0]>=a[poz[m]][1])
    {
       m++;
       poz[m]=i;                         
    }
    
	poz[0]=a[1][0];poz[m+1]=n+1;a[n+1][0]=a[n][1];
	for (i=m; i>=1; i--)
	{
		k=a[i][1]-a[i][0];
		for (j=poz[i]; j<=poz[i+1]-1; j++)
			if (a[poz[i+1]][0]>=a[j][1] && a[j][0]>=a[poz[i-1]][1] && a[j][1]-a[j][0]>k)
            {
               k=a[j][1]-a[i][0];
               poz[i]=j;                      
            }
    }
    sum=0;
    for (i=1; i<=m; i++)
        sum+=a[poz[i]][1]-a[poz[i]][0];
    
    printf("%lld\n",sum);
        
    return 0;    
}