Cod sursa(job #495498)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 25 octombrie 2010 17:05:41
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <stdio.h>
#include <deque>
#include <algorithm>
#define Nmax 100000+2

using namespace std;

deque< int > Q;
struct punct{ int x,y; } H[Nmax],V[Nmax];
int Nh,Nv,T;

inline int Maxim(int x,int y){ return x>y ? x:y; }
inline int cmp(punct a, punct b){
	return a.x<b.x || (a.x==b.x && a.y<b.y);
}

int main(){
	int i,j,nr,tall;
	freopen("hvrays.in","r",stdin);
	freopen("hvrays.out","w",stdout);
	for( scanf("%d",&T); T; --T){
		scanf("%d%d",&Nh,&Nv);
		for(i=1;i<=Nh;++i) scanf("%d%d",&H[i].x,&H[i].y);
		for(i=1;i<=Nv;++i) scanf("%d%d",&V[i].x,&V[i].y);
		sort(H+1,H+Nh+1,cmp);
		sort(V+1,V+Nv+1,cmp);
	
	while( !Q.empty() ) Q.pop_back();
	
	j=1;
	for(i=1;i<=Nv;++i){
		nr=0; tall=0;
		while( j<=Nh && H[j].x<=V[i].x && H[j].y<=V[i].y ){
			tall=Maxim(tall,H[j].y);
			++nr,++j;
		}
		
		if( Q.empty() ){
			if(nr) Q.push_back(tall);
		}
		else
			if( Q.back() <= V[i].y || nr ){
				while( !Q.empty() && Q.back() <= V[i].y ){
					tall=Maxim(tall,Q.back());
					Q.pop_back();
				}
				Q.push_back(tall);
			}
	}
	
	printf("%d\n",Q.size());
	}
	fclose(stdin); fclose(stdout);
	return 0;
}