2368805_tle.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <algorithm>
using namespace std;
int n;
struct node
{
	int a, b;
	int h;
}ret[40001];

bool cmp(struct node a,struct node b)
{
	if(a.h==b.h)
	{
		if(a.a==b.a)
			return a.b<b.b;
		else
			return a.a<b.a;
	}
	else
		return a.h<b.h;
}

int main()
{
	int i, j, next, tt;
	int t1, t2, ta;
	int ans, h, H;

	scanf("%d",&n);
	for(i = 0; i < n; i++)
		scanf("%d%d%d",&ret[i].a,&ret[i].b,&ret[i].h);
	sort(ret,ret+n,cmp);
	ans = 0;
	for(i = n-1; i >= 0; i--)
	{
		j = i-1;
		h = ret[i].h;
		while(j>=0&&ret[j].h==ret[i].h)
			j--;
		j++;
		H = h;
		if(j)
		{
			H = h-ret[j-1].h;
			for(tt = j; tt < n; tt++)
				ret[tt].h = ret[j-1].h;
		}
		next = j;
		sort(&ret[j],&ret[j]+n-j,cmp);
		ta = ret[j].a;t1 = t2 = ret[j].b;
		do
		{
			j++;
			while(j<n&&ret[j].a<t1)
			{
				if(ret[j].b>t2)
					t2 = ret[j].b;
				j++;
			}
			ans += (t2-ta)*H;
			if(j<n)
			{
				ta = ret[j].a;
				t1 = t2 = ret[j].b;
			}
		}while(j<n);
		i = next;
	}
	printf("%d\n",ans);
	return 1;
}