PKU 3168

ついにBarn Expansionが解けました。
解法：

よく考えたらこれ可変長じゃなくて入力によってサイズが変わるので二次元配列にしづらい配列の間違いでした

(もちろんvectorはTLEするし、いつもの隣接リストではソートできません)

配列のサイズが最初で全部決められて決めるのも容易だったのでこの実装方法にしてみました。
参考にどうぞ。実行時間は500msです。

#include<stdio.h>
#include<algorithm>
using namespace std;
int x1[30000];
int x2[30000];
int y1[30000];
int y2[30000];
int ok[30000];
pair<int,int> P[110000];
pair<int,int> Q[110000];
int xf[1100000];
int xs[1100000];
int yf[1100000];
int ys[1100000];
inline int ABS(int a){return max(a,-a);}
int main(){
	int a;
	scanf("%d",&a);
	for(int i=1;i<=a;i++){
		scanf("%d%d%d%d",x1+i,y1+i,x2+i,y2+i);
		xs[x1[i]]+=2;
		xs[x2[i]]+=2;
		ys[y1[i]]+=2;
		ys[y2[i]]+=2;
	}
	int nx=0;
	int ny=0;
	for(int i=0;i<1100000;i++){
		xf[i]=nx;
		nx+=xs[i];
		yf[i]=ny;
		ny+=ys[i];
		xs[i]=ys[i]=0;
	}
	for(int i=1;i<=a;i++){
		P[xf[x1[i]]+(xs[x1[i]]++)]=make_pair(y1[i],-i);
		P[xf[x1[i]]+(xs[x1[i]]++)]=make_pair(y2[i],i);
		P[xf[x2[i]]+(xs[x2[i]]++)]=make_pair(y1[i],-i);
		P[xf[x2[i]]+(xs[x2[i]]++)]=make_pair(y2[i],i);
		Q[yf[y1[i]]+(ys[y1[i]]++)]=make_pair(x1[i],-i);
		Q[yf[y1[i]]+(ys[y1[i]]++)]=make_pair(x2[i],i);
		Q[yf[y2[i]]+(ys[y2[i]]++)]=make_pair(x1[i],-i);
		Q[yf[y2[i]]+(ys[y2[i]]++)]=make_pair(x2[i],i);
	}
	for(int i=0;i<1100000;i++){
		if(xs[i])std::sort(P+xf[i],P+xf[i]+xs[i]);
		if(ys[i])std::sort(Q+yf[i],Q+yf[i]+ys[i]);
	}
	int ret=0;
	for(int i=1;i<=a;i++)ok[i]=1;
	for(int i=0;i<1100000;i++){
		for(int j=xf[i];j<xf[i]+xs[i];j++){
			if(P[j].second>0)continue;
			if(P[j].second!=-P[j+1].second){
				ok[-P[j].second]=0;
				int k=j+1;
				while(P[j].second!=-P[k].second){
					ok[ABS(P[k].second)]=0;
					k++;
				}
				j=k;
			}else j++;
		}
		for(int j=yf[i];j<yf[i]+ys[i];j++){
			if(Q[j].second>0)continue;
			if(Q[j].second!=-Q[j+1].second){
				ok[-Q[j].second]=0;
				int k=j+1;
				while(Q[j].second!=-Q[k].second){
					ok[ABS(Q[k].second)]=0;
					k++;
				}
				j=k;
			}else j++;
		}
	}
	for(int i=1;i<=a;i++)if(ok[i])ret++;
	printf("%d\n",ret);
}