Cod sursa(job #330301)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 9 iulie 2009 14:34:11
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include<cstdio>
#include<algorithm>
#define N 100002
using namespace std;
int n,a,b,s;
int max1;
struct ad{int x; bool y;}h[N];
struct heavy{int x,y;}v[N];
bool compar(const heavy&a,const heavy&b)
{
	if (a.x==b.x)
		if (a.y>=b.y) return true;
	else
		return false;
	if (a.x<=b.x) return true;
	return false;
}
void citire()
{
	freopen("heavymetal.in","r",stdin);
	freopen("heavymetal.out","w",stdout);
	scanf("%d",&n);
	for (int i=1; i<=n; ++i)
	{
		scanf("%d%d",&v[i].x,&v[i].y);
		if (max1<v[i].y) 
			max1=v[i].y;
	}
	sort(v+1,v+1+n,compar);
	for (int  i=1; i<=n; ++i)
		h[v[i].x].x=i;
}

int heavy()
{
	int j=0;
	for (int i=1; i<=n; ++i)
	{
		if (h[v[i].x].y)
			continue;
		j=b;
		a=v[i].x;
		b=v[i].y;
		while (h[b].x)
		{
			h[v[h[b].x].x].y=true;
			b=v[h[b].x].y;
			
			if (b==n)
				break;
		}
		
		if (a==v[1].x&&b==max1)
			return b-a;
		if(v[i-1].x==a)
		{
			if (j>b)
				b=j;
		}
		else
		s+=b-a;
	}
	return s;
}
int main()
{
	citire();
	printf("%d ",heavy());
	return 0;
}