Cod sursa(job #90773)

Utilizator DITzoneCAdrian Diaconu DITzoneC Data 10 octombrie 2007 11:28:46
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.92 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define nmax 200111
#define mp make_pair
#define FOR(i,s,d) for(i=(s);i<(d);++i)
#define f first
#define s second

int T,n,m,sol;
pair < pair <int,int> ,int > P[nmax];

int main()
{
    int ii,i,j,k;
    freopen("hvrays.in","r",stdin);
    freopen("hvrays.out","w",stdout);
    scanf("%d",&T);
    FOR(ii,0,T)
    {
        sol=0;
        scanf("%d %d",&n,&m);
        FOR(k,0,n)
        {
            scanf("%d %d",&i,&j);
            P[k]=mp(mp(i,0),j);
        }
        FOR(k,0,m)
        {
            scanf("%d %d",&i,&j);
            P[k+n]=mp(mp(i,1),j);
        }
        sort(P,P+n+m); reverse(P,P+n+m);
        j=k=-1;
        FOR(i,0,n+m)
        {
            if(P[i].f.s)
                j=max(j,P[i].s);
            else
                if(P[i].s>k)
                    sol++,k=j;
        }
        printf("%d\n",sol);
        
    }
    return 0;
}