Cod sursa(job #195338)

Utilizator swift90Ionut Bogdanescu swift90 Data 17 iunie 2008 19:23:07
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef pair <int,int> valori;
valori hh[100010],vv[100010];
int comp(valori a, valori b){
	if(a.first!=b.first)
		return a.first>b.first;
	return a.second<b.second;
}
int main(){
	freopen("hvrays.in","r",stdin);
	freopen("hvrays.out","w",stdout);
	int t,h,v,i,j,m,nr,pas;
	
	scanf("%d",&t);
	for(;t;--t){
		scanf("%d%d",&h,&v);
		for(i=0;i<h;++i)
			scanf("%d%d",&hh[i].first,&hh[i].second);
		for(i=0;i<v;++i)
			scanf("%d%d",&vv[i].first,&vv[i].second);
		
		sort(hh,hh+h,comp);
		sort(vv,vv+v,comp);
		
		m=0;
		nr=0;
		pas=0;
		for(i=0;i<h;++i){
			if(i==0 || m<hh[i].second){
				++nr;
				for(j=pas;j<v && vv[j].first>=hh[i].first;++j)
					m=max(m,vv[j].second);
				pas=j;
			}
		}
		printf("%d\n",nr);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}