2009 Starry Sky

Starry Sky木のもとになった問題なので当然Starry Sky木を使いますが、自明にO(N^2log N)が出てくるとして、問題はこれを定数倍改善しないと通らないということです。
このO(N^2 log N)は座標圧縮のところあたりが悪いのか、50点分しか取れないのでSegmentTree書くだけ無駄感がありますが、多分座標圧縮とかを改善するとはやくなるとおもいます。最悪ケースだと20sec程度。

#include<stdio.h>
#include<algorithm>
using namespace std;
int segtree[16384];
int L[4000];
unsigned int X[8000];
unsigned int B[4000];
unsigned int C[4000];
unsigned int D[4000];
void query(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return;
	if(c<=a&&b<=d){
		segtree[e]+=f;
	}else{
		query(a,(a+b)/2,c,d,e*2,f);
		query((a+b)/2+1,b,c,d,e*2+1,f);
	}
	if(e==1){
//		printf("%d %d\n",e,segtree[e]);
		return;
	}
	if(segtree[e]>0||segtree[e^1]>0){
		int k=max(segtree[e],segtree[e^1]);
		segtree[e/2]+=k;
		segtree[e]-=k;
		segtree[e^1]-=k;
	}else if(segtree[e]<0&&segtree[e^1]<0){
		int k=max(segtree[e],segtree[e^1]);
		segtree[e/2]+=k;
		segtree[e]-=k;
		segtree[e^1]-=k;
	}
//	printf("%d %d\n",e,segtree[e]);
}
pair<pair<unsigned int,int>,pair<unsigned int,unsigned int> >event[8000];//Y TYPE X1 X2
int main(){
	int a;
	scanf("%d",&a);
	for(int i=0;i<a;i++){
		scanf("%u%u%u",B+i,C+i,D+i);
		B[i]*=2;
		C[i]*=2;
		D[i]*=2;
		L[i]=-((int)D[i]);
		
	}
	std::sort(L,L+a);
	int ret=0;
	for(int i=0;i<a;i++){
		int size=0;
		int now=0;
		unsigned int p=(unsigned int)(-L[i]);
		for(int j=0;j<a;j++){
			if(p<=D[j]){
				if(B[j]>=p/2)X[now++]=B[j]-p/2;
				else X[now++]=0;
				X[now++]=B[j]+p/2;
				if(C[j]>=p/2)event[size++]=make_pair(make_pair(C[j]-p/2,0),make_pair(X[now-2],X[now-1]));
				else event[size++]=make_pair(make_pair(0,0),make_pair(X[now-2],X[now-1]));
				event[size++]=make_pair(make_pair(C[j]+p/2,1),make_pair(X[now-2],X[now-1]));
			}
		}
		std::sort(X,X+now);
		std::sort(event,event+size);
		
		for(int i=0;i<size;i++){
			if(!event[i].first.second){
				query(0,8191,lower_bound(X,X+now,event[i].second.first)-X,lower_bound(X,X+now,event[i].second.second)-X,1,1);
			}else{
				query(0,8191,lower_bound(X,X+now,event[i].second.first)-X,lower_bound(X,X+now,event[i].second.second)-X,1,-1);
			}
			ret=max(ret,segtree[1]);
		}
	}
	printf("%d\n",ret);
}

意外と短くかけます。