Cod sursa(job #91492)

Utilizator astronomyAirinei Adrian astronomy Data 12 octombrie 2007 17:35:08
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define x second
#define y first

vector< pair<int, int> > H, V;

int solve(void)
{
    int i, j, res = 0, xmax = -1;

    sort(H.begin(), H.end()), sort(V.begin(), V.end());

    for(j = V.size()-1, i = H.size()-1; i >= 0; i--)
     if(H[i].x <= xmax)
        continue ;
     else
        for(res++; j >= 0 && V[j].y >= H[i].y; j--)
            xmax = max(xmax, V[j].x);

    return res;
}

int main(void)
{
    freopen("hvrays.in", "rt", stdin);
    freopen("hvrays.out", "wt", stdout);

    int i, j, k, nrv, nrh, t;

    scanf("%d", &t);
    while(t--)
    {
        H.clear(), V.clear();
        scanf("%d %d\n", &nrh, &nrv);
        for(i = 0; i < nrh; i++)
            scanf("%d %d", &j, &k), H.pb(mp(k,j));
        for(i = 0; i < nrv; i++)
            scanf("%d %d", &j, &k), V.pb(mp(k,j));
        printf("%d\n", solve());
    }

    return 0;
}