Cod sursa(job #481629)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 31 august 2010 23:45:43
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.94 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "hvrays.in"
#define file_out "hvrays.out"

#define nmax 101000

int h,v;
int T;
pair<int,int> H[nmax];
pair<int,int> V[nmax];

int solve(){
	
	sort(H,H+h);
	sort(V,V+v);
	
	int i,j=v-1,q=-1,sol=0;
	for (i=h-1;i>=0;--i)
		 if (H[i].second>q)
		 {
			 sol++;
			 while(j>=0 && H[i].first<=V[j].first)
			 {
				 q=max(q,V[j].second);
				 j--;
			 }
		 }
		 
	return sol;
}


void adfile(void){
	
	int x,y;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	
	scanf("%d\n", &T);
	while(T--)
	{
	scanf("%d %d", &h, &v);
	for (int i=0;i<h;++i)
	{
		scanf("%d %d", &x, &y);
		H[i]=make_pair(x,y);
	}
	for (int i=0;i<v;++i)
	{
		scanf("%d %d", &x, &y);
		V[i]=make_pair(x,y);
	}
	printf("%d\n", solve());
	}
	
	fclose(stdin);
	
	return ;
	
}

			 
	

int main(){
	
	adfile();
	solve();
	
	return 0;
	
}