Cod sursa(job #484296)

Utilizator darrenRares Buhai darren Data 13 septembrie 2010 15:00:19
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include <fstream>
#include <algorithm>
#include <functional>
#include <utility>

using namespace std;

int t;
int n, m;
pair<int, int> v1[100002], v2[100002];

int main()
{
	ifstream fin("hvrays.in");
	ofstream fout("hvrays.out");

	fin >> t;

	while (t--)
	{
		fin >> n >> m;
		for (int i = 1; i <= n; ++i)
			fin >> v1[i].first >> v1[i].second;
		for (int i = 1; i <= m; ++i)
			fin >> v2[i].first >> v2[i].second;

		sort(v1 + 1, v1 + n + 1, greater<pair<int, int> >());
		sort(v2 + 1, v2 + m + 1, greater<pair<int, int> >());

		int ymax = -1, need = 0;
		int i = 1, j = 1;

		while (i <= n)
		{
			while (ymax >= v1[i].second && i <= n) ++i;
			if (i == n + 1) break;

			while (v2[j].first >= v1[i].first)
			{
				ymax = max(ymax, v2[j].second);
				++j;
			}
			++need;
		}

		fout << need << '\n';
	}

	fin.close();
	fout.close();
}