2009 Starry Sky

同じ記事を前に書いたらしいです。

以前適当に書いて64点しか取れなかったので、本気で定数倍改善することにしました。やったことは、

・イベントを毎回ソートするのをやめる
・座標圧縮の座標を毎回ソートしてきめるのをやめる
・座標でどこに配置されるかを決めるのに毎回lower_boundを使うのをやめる
・SegmentTreeの更新に再帰を使うのをやめる
・maxをinline化する
・2回のSegmentTreeの更新の動作を1つにまとめる
・ビット演算を使いまくる
・if(y&1)segtree[y^1]++;をsegtree[y^1]+=y&1;に変える(ifを消す)　！重要！

こんなことをやってようやく通りました。それにしてもなぜ最後の改善(if消し)で3000MSのTimeLimitに間に合わなかったものが1999MSで終わるようになってしまったのだろう……
O(N^2 log N)ですがO(N^2 log N)の部分はSegmentTreeの更新だけにします。

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef unsigned int wolf;
inline int Max(int a,int b){return a<b?b:a;}
int segtree[16384];
int L[4000];
wolf X[8000];
wolf B[4000];
wolf C[4000];
wolf D[4000];
pair<wolf,int >S[4000];//Y TYPE X1 X2 tasu hou
pair<wolf,int>F[4000];
pair<wolf,wolf>G[4000];
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]<<=1;
		C[i]<<=1;
		D[i]<<=1;
		L[i]=-((int)D[i]);
		F[i]=make_pair(B[i],i);
	}
	std::sort(L,L+a);
	for(int i=0;i<a;i++){
		S[i]=make_pair(C[i],i);
	}
	std::sort(S,S+a);
	std::sort(F,F+a);
	int ret=0;
	for(int i=0;i<a;i++){
		int size=0;
		int now=0;
		wolf p=(wolf)(-L[i]);
		if(i&&L[i]==L[i-1])continue;
		int nowE=0;
		int nowF=0;
		int nowS=0;
		int nowT=0;
		int A=a<<1;
		for(int j=0;j<A;j++){
			if(nowF==a||(nowE<a&&F[nowE].first<=F[nowF].first+p)){
				if(p<=D[F[nowE].second])X[now++]=F[nowE].first;
				G[F[nowE].second].first=j;
				nowE++;
			}else{
				if(p<=D[F[nowF].second])X[now++]=F[nowF].first+p;
				G[F[nowF].second].second=j;
				nowF++;
			}
		}
		for(int j=0;j<A;j++){
			if(nowT==a||(nowS<a&&S[nowS].first<=S[nowT].first+p)){
				if(p<=D[S[nowS].second]){
					int y=G[S[nowS].second].second+1;
					int z=G[S[nowS].second].first;
					y|=1<<13;
					z|=1<<13;
					int k;
					while(y){
						segtree[y^1]+=y&1;
						segtree[z^1]-=z&1;
						if(y>1){
							k=Max(segtree[y],segtree[y^1]);
							segtree[y>>1]+=k;
							segtree[y]-=k;
							segtree[y^1]-=k;
							k=Max(segtree[z],segtree[z^1]);
							segtree[z>>1]+=k;
							segtree[z]-=k;
							segtree[z^1]-=k;
						}
						y>>=1;
						z>>=1;
					}
				}
				nowS++;
			}else{
				if(p<=D[S[nowT].second]){
					int y=G[S[nowT].second].second+1;
					int z=G[S[nowT].second].first;
					y|=1<<13;
					z|=1<<13;
					int k;
					while(y){
						segtree[y^1]-=y&1;
						segtree[z^1]+=z&1;
						if(y>1){
							k=Max(segtree[y],segtree[y^1]);
							segtree[y>>1]+=k;
							segtree[y]-=k;
							segtree[y^1]-=k;
							k=Max(segtree[z],segtree[z^1]);
							segtree[z>>1]+=k;
							segtree[z]-=k;
							segtree[z^1]-=k;
						}
						y>>=1;
						z>>=1;
					}
				}
				nowT++;
			}
			ret=Max(ret,segtree[1]);
		}
	}
	printf("%d\n",ret);
}

本気で定数倍改善したわりにまともな長さのコードになった。