Cod sursa(job #181780)

Utilizator vlad_popaVlad Popa vlad_popa Data 18 aprilie 2008 22:30:38
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define pct pair <int, int>
#define MAXN 1<<17
#define x first
#define y second
#define INF 0x3f3f3f3f

pct H[MAXN], V[MAXN];
int N, M;

void read ()
{
    int i, j;
    
    scanf ("%d %d", &N, &M);
    for (i = 1; i <= N; ++ i)
        scanf ("%d %d", &H[i].x, &H[i].y);
    for (i = 1; i <= M; ++ i)
        scanf ("%d %d", &V[i].x, &V[i].y);
}

void solve ()
{
    int i, j;
    sort (H + 1, H + N + 1);
    sort (V + 1, V + M + 1);
    
    int Vmax = -INF, sol = 0;
    for (i = N, j = M; i >= 1; -- i)
        if (H[i].y > Vmax)
        {
            for (; j >= 1 && V[j].x >= H[i].x; -- j)
                Vmax = max(Vmax, V[j].y);
            //printf ("%d ", i);
            ++ sol;
        }
    printf ("%d\n", sol);
}

int
 main ()
{
    freopen ("hvrays.in", "rt", stdin);
    freopen ("hvrays.out", "wt", stdout);
    
    int T;
    for (scanf("%d", &T); T; --T)
    {
        read ();
        solve ();
    }
    
    return 0;
}