Starry Sky Tree

StarrySkyを解こうとしました．
枝刈りしていないので半分ぐらいTLEします．

#include <cstdio>
#include <string.h>
#include <algorithm>
#define X first
#define Y second
using namespace std;
const int MAXN = 4096;
typedef pair<int, int> P;
typedef pair<P, int> STAR;
int N;
int cx[MAXN], cy[MAXN], cl[MAXN];
STAR stars[MAXN];
const int INF = 1 << 29;
int sst[MAXN * 2 - 1];
int adt[MAXN * 2 - 1];
void init(){
	fill(sst,sst+MAXN*2-1,0);
	fill(adt,adt+MAXN*2-1,0);
}
//区間[p,q)に値xを加算
void add(int p, int q, int x, int k, int l, int r){
	if(r <= p || q <= l) return;
	if(p <= l && r <= q){
		adt[k] += x;
		return;
	}
	add(p, q, x, 2*k+1, l, (l+r)/2);
	add(p, q, x, 2*k+2, (l+r)/2, r);
	sst[k]=max(sst[2*k+1]+adt[2*k+1],sst[2*k+2]+adt[2*k+2]);
}
int get_max(int p, int q, int k, int l, int r){
	if(r <= p || q <= l) return -INF;
	if(p <= l && r <= q) return sst[k]+adt[k];
	int m1, m2;
	m1 = get_max(p,q,2*k+1,l,(l+r)/2);
	m2 = get_max(p,q,2*k+2,(l+r)/2,r);
	return max(m1,m2)+adt[k];
}
int conv(int v, int c[MAXN]){
	return distance(c,lower_bound(c,c+N,v));
}
int main(){
	scanf("%d", &N);
	for(int i = 0; i < N; i++){
		int x, y, l;
		scanf("%d %d %d", &x, &y, &l);
		stars[i] = STAR(P(x,y),l);
		cx[i] = x;
		cy[i] = y;
		cl[i] = l;
	}
	sort(cx,cx+N); sort(cy,cy+N); sort(cl,cl+N);
	sort(stars, stars+N);
	int ans = 0;
	for(int L = 0; L < N; L++){
		int lx = 0, rx = 0;
		init();
		for(; rx<N; rx++){
			if(cl[L] <= stars[rx].second){
				int ry = conv(stars[rx].first.Y, cy) + 1;
				int ly = conv(stars[rx].first.Y - cl[L], cy);
				add(ly, ry, 1, 0, 0, MAXN);
			}
			for(; cx[rx]-cx[lx] > cl[L]; lx++){
				if(cl[L] <= stars[lx].second){
					int ry = conv(stars[lx].first.Y, cy) + 1;
					int ly = conv(stars[lx].first.Y - cl[L], cy);
					add(ly, ry, -1, 0, 0, MAXN);
				}
			}
			ans = max(ans, get_max(0,MAXN,0,0,MAXN));
		}
	}
	printf("%d\n", ans);
}