Cod sursa(job #468897)

Utilizator mihai995mihai995 mihai995 Data 5 iulie 2010 13:24:37
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <fstream>
using namespace std;

struct timp{int x,val;};
const int etc=1000000001;
timp v[1<<18];
int n;

ifstream in("heavymetal.in");
ofstream out("heavymetal.out");

bool cmp(timp a,timp b)
{
	return a.x<b.x || a.x==b.x && a.val>b.val;
}

int main()
{
	in>>n;n<<=1;
	int i,nr=0;
	for (i=1;i<=n;i+=2)
	{
		in>>v[i].x>>v[i+1].x;
		v[i].val=1;v[i+1].val=-1;
	}
	sort(v+1,v+n+1,cmp);
	for (i=n;i;i--)
		if (v[i].x==v[i-1].x)
		{
			v[i-1].val+=v[i].val;
			v[i].x=etc;
			nr++;
		}
	sort(v+1,v+n+1,cmp);
	n-=nr;nr=0;
	for (i=1;i<=n;i++)
	{
		v[i].val+=v[i-1].val;
		if (v[i-1].val)
			nr+=v[i].x-v[i-1].x;
	}
	out<<nr<<"\n";
	return 0;
}