2012 ACM/ICPC Asia Regional Changchun Online-1022

//http://acm.hdu.edu.cn/showproblem.php?pid=4268
//アイデアの問題は、試合前にできなかったです.先輩の話を聞いて、欲張りです.その中の一つで並べ替えて、後はもう一つの維貪欲です.その維の上で一番近いのを探せばいいです.探している時に線分の木を守って、直接に一番近いのを探せばいいです.
//コードは以下の通りです
 

#include<stdio.h>
#include<map>
#include<algorithm>
using namespace std;
struct node
{
	int x,y;
};
node al[110000],bob[110000];
bool cmp(node a,node b)
{return a.x<b.x||(a.x==b.x&&a.y<b.y);}
int sum[410000],n,yy[110000],y1[110000];
map <int,int> pos1,pos2;
void update(int i,int l,int r,int p,int v)
{
	int mid=(l+r)>>1;
	sum[i]+=v;
	if(l==r)return;
	else 
	{
		if(p<=mid)update(i<<1,l,mid,p,v);
		else update(i<<1|1,mid+1,r,p,v);
	}
}
int query(int i,int l,int r,int a,int b)
{
	int mid=(l+r)>>1;
	if(a>b)return 0;
	if(a==l&&b==r)
		return sum[i];
	else 
	{
		if(b<=mid)
			return query(i<<1,l,mid,a,b);
		else if(b>mid&&a<=mid)
			return query(i<<1,l,mid,a,mid)+query(i<<1|1,mid+1,r,mid+1,b);
		else return query(i<<1|1,mid+1,r,a,b);
	}
}
int find(int i,int l,int r,int p)
{
	int mid=(l+r)>>1;
	if(l==r)return l;
	else 
	{
		if(p<=sum[i<<1])
			return find(i<<1,l,mid,p);
		else return find(i<<1|1,mid+1,r,p-sum[i<<1]);
	}
}
int main()
{
	int cas,i,ant,cnt,j;
	scanf("%d",&cas);
	while(cas--)
	{
		pos1.clear();
		pos2.clear();
		scanf("%d",&n);
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&al[i].x,&al[i].y);
			y1[i]=al[i].y;
		}
		for(i=1;i<=n;i++)
		{
			scanf("%d%d",&bob[i].x,&bob[i].y);
			yy[i]=bob[i].y;
		}
		sort(al+1,al+n+1,cmp);
		sort(bob,bob+n+1,cmp);
		sort(yy+1,yy+n+1);
		sort(y1+1,y1+n+1);
		for(i=1;i<=n;i++)
			pos1[yy[i]]=i;
		for(i=1,j=1;i<=n;i++)
		{
			for(;j<=n;j++)
				if(y1[i]<yy[j])
					break;
			pos2[y1[i]]=j-1;
		}
		cnt=0;
		memset(sum,0,sizeof(sum));
		for(i=1,j=1;i<=n;i++)
		{
			for(;j<=n;j++)
			{
				if(al[i].x<bob[j].x)
					break;
				update(1,1,n,pos1[bob[j].y],1);
			}
			ant=query(1,1,n,1,pos2[al[i].y]);
			if(ant)
			{
				ant=find(1,1,n,ant);
				update(1,1,n,ant,-1);
				cnt++;
			}
		}
		printf("%d
",cnt);
	}
	return 0;
}