Cod sursa(job #487386)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 24 septembrie 2010 23:09:26
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.77 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define nmax 100010

int n, m, sol, t;

struct nr
{
	int x, y;
} a[nmax], b[nmax];

int cmp(nr a, nr b)
{
	if (a.y!=b.y) return a.y>b.y;
	return a.x>b.x;
}

int main()
{
	freopen("hvrays.in","r",stdin);
	freopen("hvrays.out","w",stdout);
	scanf("%d",&t);
	int i, j, x;
	while (t--)
	{
		scanf("%d %d",&n,&m);
		for (i=1; i<=n; i++) scanf("%d %d",&a[i].x,&a[i].y);
		for (i=1; i<=m; i++) scanf("%d %d",&b[i].x,&b[i].y);
		sort(a+1, a+n+1, cmp);
		sort(b+1, b+m+1, cmp);
		sol=0;
		for (i=j=1; i<=n; )
		{
			x=b[j].x;
			for (; j<=m; j++)
			{
				if (b[j].y<a[i].y) break;
				if (b[j].x>x) x=b[j].x;
			}
			while (x>=a[i].x && i<=n) i++;
			sol++;
		}
		printf("%d\n",sol);
	}
}