2369047_tle.cc

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

#include <algorithm> 
using namespace std;
#define INIT (Ret *)malloc(sizeof(Ret))

typedef struct node
{
	int a, b;
	int h;
	struct node *next;
}Ret;

Ret *head;
int H[40001];
int n;

int main()
{
	int i, th, tmp;
	Ret *s, *p;
	int l, r, tr;
	int ans = 0;
	int a, b, h;

	scanf("%d",&n);
	head = INIT;
	head->next = NULL;
	for(i = 0; i < n; i++)
	{
		scanf("%d%d%d",&a,&b,&h);
		H[i] = h;
		s = head;

		while(s->next)
		{
			if(s->next->a>=a)
				break;
			else
				s = s->next;
		}
		p = INIT;
		p->a = a;p->b = b;p->h = h;
		p->next = s->next;
		s->next = p;
	}
	sort(H,H+n);
	tmp = 0;
	for(i = 0; i < n; i++)
	{
		H[i] -= tmp;
		th = H[i];
		s = head;
		while(1)
		{
			l = s->next->a;r = tr = s->next->b;
			while(s->next&&s->next->a<=tr)
			{
				if(s->next->b>r)
					r = s->next->b;
				if(s->next->h==th)
					s->next = s->next->next;
				else
					s->next->h -= th,s = s->next;
			}
			ans += th*(r-l);
			if(!s->next)
				break;
		}
		tmp += th;
		while(H[i]==th)
			i++;
		i--;
	}
	printf("%d\n",ans);
	return 1;
}