133.c

来自「平时acm训练时ac的源代码」· C语言 代码 · 共 106 行

/* 133
Accepted 141 ms 362 kb 
*/
#include <stdlib.h>
#include <stdio.h>

typedef struct Border
{
	long A, B;
}Border;

int LQ(Border i, Border j)
{
	if (i.A<j.A)
	{
		return 1;
	}
	else if (i.A>j.A)
	{
		return 0;
	}
	else if (i.B<j.B)
	{
		return 1;
	}
	else
	{
		return 0;
	}
}


void Merge(Border r[] , int low , int m , int high)
{
    int i=low , j=m+1 , p=0 ;
	Border *r1 ;

	r1 = (Border *)malloc((high-low+1)*sizeof(Border)); 

	while(i<=m && j<=high)
		r1[p++] = (LQ(r[i], r[j]))?r[i++]: r[j++];

    while(i<=m)
		r1[p++] = r[i++];

    while(j<=high)
		r1[p++] = r[j++];

    for(p=0 , i=low ; i<=high ; p++, i++)
		r[i] = r1[p];

	free(r1);
}

void MergePass(Border r[] , int length, int n)
{
	int i ;
	for(i=0;i+2*length-1<=n;i=i+2*length)
		Merge(r , i , i+length-1 , i+2*length-1);
	if(i+length-1<n)
		Merge(r , i , i+length-1 , n);
}

void MergeSort(Border a[], int n)
{
	int length;
	for(length=1;length<n;length*=2)
		MergePass(a, length, n-1);
}

int main(void)
{
	int N, count=0, i, l, r;
	Border *B;
	scanf("%d", &N);
	B = (Border *)malloc(sizeof(Border)*N);
	for (i=0; i<N; i++)
	{
		scanf("%ld %ld", &(B[i].A), &(B[i].B));
	}
	MergeSort(B, N);
	l = B[0].A;
	r = B[0].B;
	for (i=1; i<N; i++)
	{
		if (B[i].A==l)
		{
			if (r<B[i].B)
			{
				r = B[i].B;
			}
		}
		else if (B[i].B<r)
		{
			count += 1;
		}
		else
		{
			l = B[i].A;
			r = B[i].B;
		}
	}
	printf("%d", count);
	free(B);
}