Cod sursa(job #137375)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 17 februarie 2008 11:47:36
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda preONI 2008, Runda 4, Clasele 5-8 Marime 0.75 kb
#include <stdio.h>
#include <stdlib.h>

int n, s1;

typedef struct 
{
	int x, y;
} interval;
interval a[100000], b[100000];

int cmp(const void *a, const void *c)
{
	int i = *(int*)a, j = *(int*)c;
	if (b[i].x == b[j].x) return b[j].y - b[i].y;
	else return b[i].x - b[j].x;
}

int main()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	int i, ord[100000];
	interval x;
	scanf("%d",&n);
	for (i = 0; i < n; i++){ scanf("%d %d",&b[i].x, &b[i].y); ord[i] = i;}

	qsort(ord,n,sizeof(int),cmp);
	for (i = 1; i <= n; i++) a[i] = b[ord[i-1]];

	x = a[1]; s1 = x.y - x.x;
	for (i = 2; i <= n; i++)
	{
		if (a[i].x >= x.y)
		{
			x = a[i];
			s1 += (x.y - x.x);
		}
	}
	printf("%d\n",s1);
	return 0;
}