Cod sursa(job #97037)

Utilizator sealTudose Vlad seal Data 4 noiembrie 2007 19:12:15
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
using namespace std;
#include<cstdio>
#include<algorithm>
#include<utility>
#define Nm (1<<17)
#define min(a,b) ((a)<(b)?(a):(b))
int h,v;
pair<int,int> H[Nm],V[Nm];

void read()
{
    char S[20];
    int i,j,x,y;

    scanf("%d%d ",&h,&v);
    for(i=0;i<h;++i)
    {
        gets(S);
        for(x=j=0;S[j]!=' ';++j)
            x=x*10+S[j]-'0';
        for(y=0,++j;S[j];++j)
            y=y*10+S[j]-'0';
        H[i]=make_pair(x,y);
    }
    
    for(i=0;i<v;++i)
    {
        gets(S);
        for(x=j=0;S[j]!=' ';++j)
            x=x*10+S[j]-'0';
        for(y=0,++j;S[j];++j)
            y=y*10+S[j]-'0';
        V[i]=make_pair(x,y);
    }
}

int solve()
{
    int i,j=v-1,ym=-1,ans=0;

    sort(H,H+h);
    sort(V,V+v);

    for(i=h-1;i>=0;--i)
        if(H[i].second>ym)
        {
            ++ans;
            for(;j>=0 && V[j].first>=H[i].first;--j)
                ym=max(ym,V[j].second);
        }
    return ans;
}

int main()
{
    int t;

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

    scanf("%d",&t);
    while(t--)
    {
        read();
        printf("%d\n",solve());
    }
    return 0;
}