1154.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1154 on 2005-12-01 at 22:37:57 */ 
#include <cstdio>
#include <cstdlib>

const int MAX = 10240;

class Edge {
public:
	int x, high;
	bool enter;
	void init(int, int, bool);
};
void Edge::init(int cx, int h, bool e) {
	x = cx;
	high = h;
	enter = e;
}

class LineTree {
private:
	LineTree *left;
	LineTree *right;
	int cover, x, y;
	void update();
public:
	int cl;
	LineTree(int, int);
	void insert(int, int);
	void del(int, int);
};
void LineTree::update() {
	if(cover > 0) {
		cl = y - x;
	} else if(y - x == 1) {
		cl = 0;
	} else {
		cl = left->cl + right->cl;
	}
}
LineTree::LineTree(int l, int r) {
	x = l;
	y = r;
	cl = cover = 0;
	if(y != x + 1) {
		int m = (x + y) / 2;
		left = new LineTree(x, m);
		right = new LineTree(m, y);
	} else {
		left = right = NULL;
	}
}
void LineTree::insert(int l, int r) {
	if(l <= x && y <= r) {
		cover++;
	} else {
		if(l < (x + y) / 2) {
			left->insert(l, r);
		}
		if(r > (x + y) / 2) {
			right->insert(l, r);
		}
	}
	update();
}
void LineTree::del(int l, int r) {
	if(l <= x && y <= r) {
		cover--;
	} else {
		if(l < (x + y) / 2) {
			left->del(l, r);
		}
		if(r > (x + y) / 2) {
			right->del(l, r);
		}
	}
	update();
}

int cmp(const void*, const void*);

int main()
{
	LineTree building(0, MAX);
	Edge edge[MAX];
	char line[MAX];
	int xa, h, xb;
	int n, i;
	
	for(n = 0; gets(line) != NULL; n++) {
		sscanf(line, "%d %d %d", &xa, &h, &xb);
		edge[2*n].init(xa, h, xa <= xb);
		edge[2*n+1].init(xb, h, xa > xb);
	}
	int m = 2 * n, ph = 0;
	qsort(edge, m, sizeof(Edge), cmp);
	bool print = false;
	for(i = 0; i < m; i++) {
		if(edge[i].enter) {
			building.insert(0, edge[i].high);
		} else {
			building.del(0, edge[i].high);
		}
		if(building.cl != ph && (i == m-1 || edge[i].x != edge[i+1].x)) {
			if(print) {
				putchar(' ');
			}
			print = true;
			printf("%d %d", edge[i].x, building.cl);
			ph = building.cl;
		}
	}
	putchar('\n');
	
	return 0;
}

int cmp(const void* a, const void* b)
{
	Edge *x = (Edge*)a, *y = (Edge*)b;
	
	if(x->x != y->x) {
		return (x->x - y->x);
	} else {
		return (x->high - y->high);
	}
}