Cod sursa(job #91375)

Utilizator gcosminGheorghe Cosmin gcosmin Data 12 octombrie 2007 11:24:49
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

#define NMAX 100010

int T, H, V;

pair <int, int> hh[NMAX];
pair <int, int> vv[NMAX];

inline int MAX(int a, int b) { return (a > b) ? a : b; }

int cmp(pair<int, int> a, pair<int, int> b)
{
	if (a.second == b.second) return a.first > b.first;
	return a.second > b.second;
}

int main()
{
	int i, j;

	freopen("hvrays.in", "r", stdin);
	freopen("hvrays.out", "w", stdout);

	for (scanf("%d", &T); T; T--) {
		scanf("%d %d", &H, &V);

		for (i = 1; i <= H; i++) scanf("%d %d", &hh[i].first, &hh[i].second);
		for (i = 1; i <= V; i++) scanf("%d %d", &vv[i].first, &vv[i].second);

		sort(hh + 1, hh + H + 1, cmp);
		sort(vv + 1, vv + V + 1, cmp);

		int mluat = -1, mpos = -1, nr = 0;
		j = 1;

		for (i = 1; i <= H; i++) {
			for (; j <= V && vv[j].second >= hh[i].second; j++) mpos = MAX(mpos, vv[j].first);

			if (hh[i].first > mluat) {
				mluat = mpos;
				nr++;
			}
		}

		printf("%d\n", nr);
	}

return 0;
}