Cod sursa(job #554504)

Utilizator tudorsTudor Siminic tudors Data 14 martie 2011 21:37:12
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <stdio.h>
#include <algorithm>
#define N 100001
using namespace std;

typedef struct {int st,dr;} INTERVAL;
int n,rez;
INTERVAL A[N];
FILE *f,*g;

bool operator < (const INTERVAL &a, const INTERVAL &b)
{
	if (a.st<b.st)
		return 1;
	else if (a.st==b.st)
		if (a.dr<b.dr)
			return 1;
	return 0;
}

void citire()
{
	int i;
	fscanf(f,"%d",&n);
	for (i=1;i<=n;++i)
		fscanf(f,"%d %d",&A[i].st,&A[i].dr);
}

int maxim(int a, int b)
{
	if (a>=b)
		return a;
	else
		return b;
}

void solve()
{
	int mi,ma,i;
	sort(A+1,A+n+1);
	rez=0;
	mi=A[1].st;
	ma=A[1].dr;
	for (i=2;i<=n;++i)
		if (A[i].st>=ma)
		{
			rez+=ma-mi;
			mi=A[i].st;
			ma=A[i].dr;
		}
		else
			ma=maxim(ma,A[i].dr);
	rez+=ma-mi;
	fprintf(g,"%d",rez);
}

int main()
{
	f=fopen("heavymetal.in","r");
	g=fopen("heavymetal.out","w");
	
	citire();
	solve();
	
	fclose(f);
	fclose(g);
	return 0;
}