Cod sursa(job #330286)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 9 iulie 2009 13:45:32
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include<cstdio>
#include<algorithm>
#define N 100002
using namespace std;
int n,a,b,s;
int max1;
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);
}
int caut(int x, int p)
{
	int u=n,m;
	while (p!=u)
	{
		m=(p+u)/2;
		if (v[m].x>=x)
			u=m;
		else
			p=m+1;
	}
	while (p&&v[p-1].x==x)
		--p;
	if (v[p].x==x)
		return p;
	return -1;
}
int heavy()
{
	int j=0;
	for (int i=1; i<=n; ++i)
	{
		j=b;
		a=v[i].x;
		b=v[i].y;
		j=0;
		int g=caut(b,i);
		while (g!=-1)
		{
			b=v[i].y;
			if (g!=n)
			g=caut(b,g);
			else
				g=-1;
		}
		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;
}