JOI春合宿 2009-day4 Starry Sky

問題文 : 星空

解法 :
N個ある各星のLについて, そのLで囲める星の最大値を求める.

ここで, 走査をする際に, x軸のみを走査し, y軸はセグメント木で, "ある点に於いて観測できる星の最大値"を管理すると, x軸の走査がO(N), その過程でのセグメント木の走査がO(logN)で実現でき, O(N^2logN)時間でこの問題を解くことが出来る.

ただし, O(N^2logN)解法でも, 頑張って枝を狩らないと3secには間に合わないと考えられる. (僕の場合, 大きなケースでは4sec前後かかってしまいます...)

コード :

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

#define MAX_N (4000)

using namespace std;

struct Star {
	int x, y, l;
	int my;
};

int segMax[1 << 13], segAdd[1 << 13];

void add(int a, int b, int x, int k = 0, int l = 0, int r = 1 << 12)
{
	if (b <= l || r <= a) return;
	
	if (a <= l && r <= b){
		segAdd[k] += x;
		while (k){
			k = (k - 1) / 2;
			segMax[k] = max(segMax[k * 2 + 1] + segAdd[k * 2 + 1], segMax[k * 2 + 2] + segAdd[k * 2 + 2]);
		}
		return;
	}
	add(a, b, x, k * 2 + 1, l, (l + r) / 2);
	add(a, b, x, k * 2 + 2, (l + r) / 2, r);
}

bool cmpx(const Star &a, const Star &b)
{
	return (a.x < b.x);
}

bool cmpl(const Star &a, const Star &b)
{
	return (a.l < b.l);
}

int main()
{
	int n;
	int ys[MAX_N], unq[MAX_N], x[MAX_N];
	Star dat[MAX_N], datl[MAX_N];
	map<int, int> conv;
	
	scanf("%d", &n);
	
	for (int i = 0; i < n; i++){
		scanf("%d %d %d", &dat[i].x, &dat[i].y, &dat[i].l);
		ys[i] = dat[i].my = dat[i].y;
		x[i] = dat[i].x;
	}
	
	sort(ys, ys + n);
	sort(x, x + n);
	
	int idx = 0;
	conv[ys[0]] = idx;
	unq[idx++] = ys[0];
	for (int i = 1; i < n; i++){
		if (ys[i] != ys[i - 1]){
			conv[ys[i]] = idx;
			unq[idx++] = ys[i];
		}
	}
	
	for (int i = 0; i < n; i++){
		dat[i].y = conv[dat[i].y];
		datl[i] = dat[i];
	}
	
	sort(dat, dat + n, cmpx);
	sort(datl, datl + n, cmpl);
	reverse(datl, datl + n);
	
	int res = 0;
	for (int i = 0; i < n; i++){
		int L = datl[i].l;
		int head = lower_bound(x, x + n, datl[i].x - L) - x;
		int tail = head;
		memset(segMax, 0, sizeof(segMax));
		memset(segAdd, 0, sizeof(segAdd));
		while (head != n){
			while (dat[head].x - dat[tail].x > L){
				if (dat[tail].l >= L) add(dat[tail].y, upper_bound(unq, unq + idx, dat[tail].my + L) - unq, -1);
				tail++;
			}
			if (dat[tail].x > datl[i].x) break;
			
			if (dat[head].l >= L){
				add(dat[head].y, upper_bound(unq, unq + idx, dat[head].my + L) - unq, 1);
			}
			res = max(res, segMax[0] + segAdd[0]);
			head++;
		}
	}
	
	printf("%d\n", res);
	
	return (0);
}