Cod sursa(job #92729)

Utilizator filipbFilip Cristian Buruiana filipb Data 16 octombrie 2007 17:26:37
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

#define maxim(a, b) ((a > b) ? a : b)
#define INF 2000000001
#define x first
#define y second
#define NMax 100005

int Max[NMax];
pair<int, int> HH[NMax], VV[NMax], hor[NMax], ver[NMax], I[NMax];

int cmp_h(const pair<int, int>& a, const pair<int, int>& b)
{
    return (a.y > b.y) || (a.y == b.y && a.x > b.x);
}

int cmp_v(const pair<int, int>& a, const pair<int, int>& b)
{
    return (a.x < b.x) || (a.x == b.x && a.y > b.y);
}


int main(void)
{
    int T, H, V, i, j, cnt = 0;
    
    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].x, &HH[i].y);
        for (i = 1; i <= V; i++)
            scanf("%d %d", &VV[i].x, &VV[i].y);

        sort(HH+1, HH+H+1, cmp_h);
        sort(VV+1, VV+V+1, cmp_v);

        for (i = 1, j = 0; i <= H; i++)
            if (!j || HH[i].x > hor[j].x && HH[i].y < hor[j].y)
                hor[++j] = HH[i];
        H = j;

        for (i = 1, j = 0; i <= V; i++)
            if (!j || VV[i].x > ver[j].x && VV[i].y < ver[j].y)
                ver[++j] = VV[i];
        V = j;

        hor[0].x = -INF; hor[0].y = INF;

        for (i = 1; i <= V; i++)
        {
            I[i].y = I[i-1].y;
            while (I[i].y < H && hor[I[i].y+1].x <= ver[i].x)
                I[i].y++;
        }

        for (i = 1; i <= V; i++)
            I[i].y++;

        I[V+1].x = H+1;
        for (i = V; i >= 1; i--)
        {
            I[i].x = I[i+1].x;
            while (I[i].x > 1 && hor[I[i].x-1].y <= ver[i].y)
                I[i].x--;
        }

        memset(Max, 0, sizeof(Max));
        for (i = 1, j = 1; i <= H; i++)
        {
            while (i == I[j].x)
                Max[i] = maxim(Max[i], I[j].y),
                j++;
        }

        for (i = 2; i <= H; i++)
            Max[i] = maxim(Max[i], Max[i-1]);

        cnt = 0; i = 1;
        while (i <= H)
            i = Max[i], cnt++;

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

    return 0;
}