1925.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/*  This Code is Submitted by wywcgs for Problem 1925 on 2006-08-25 at 02:49:13 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 16384;
const int NN = 4*N;

class Mine {
public:
	int x, y;
	void make() { scanf("%d %d", &x, &y); }
};

class Event {
public:
	int y, o;
	bool ent;
	void set(int cy, int co, bool e) { y = cy; o = co; ent = e; }
	bool operator <(const Event& e) const { return y < e.y; }
};

int sum[NN], lmax[NN], rmax[NN], tmax[NN];

int disperse(int*, int*);
void insert(int, int, int, int, int);

int main()
{
	int x[2*N], w, h, n;
	Event e[2*N];
	Mine m[N];

	while(scanf("%d %d", &w, &h) != EOF) {
		scanf("%d", &n);
		for(int i = 0; i < n; i++) m[i].make();
		for(int i = 0; i < n; i++) {
			e[2*i].set(m[i].y, i, true); e[2*i+1].set(m[i].y+h+1, i, false);
			x[2*i] = m[i].x; x[2*i+1] = m[i].x+w+1;
		}
		int en = n << 1, j;
		int xn = disperse(x, x+en), best = 0;
		sort(e, e+en);
		memset(sum, 0, sizeof(int)*2*xn);
		for(int i = 0; i < en; i = j) {
			for(j = i; j < en && e[i].y == e[j].y; j++) {
				int o = e[j].o, x1 = lower_bound(x, x+xn, m[o].x)-x, 
					x2 = lower_bound(x, x+xn, m[o].x+w+1)-x;
				if(e[j].ent) { insert(0, x1, 1, 0, xn); insert(0, x2, -1, 0, xn); }
				else { insert(0, x1, -1, 0, xn); insert(0, x2, 1, 0, xn); }
			}
			best >?= tmax[0];
		}
		printf("%d\n", best);
	}

	return 0;
}

int disperse(int* b, int* e)
{
	int n = e-b, dn = 1;
	sort(b, e);
	for(int i = 1; i < n; i++)
		if(b[i] != b[i-1]) b[dn++] = b[i];
	return dn;
}
void insert(int o, int px, int v, int x, int y)
{
	int l = 2*o+1, r = 2*o+2;
	if(y-x == 1) { sum[o] += v; lmax[o] = rmax[o] = tmax[o] = sum[o]; return; }
	if(px < (y+x)/2) insert(l, px, v, x, (y+x)/2);
	else insert(r, px, v, (y+x)/2, y);
	sum[o] += v;
	tmax[o] = max(rmax[l]+lmax[r], max(tmax[l], tmax[r]));
	lmax[o] = max(lmax[l], sum[l]+lmax[r]);
	rmax[o] = max(rmax[r], rmax[l]+sum[r]);
}