Cod sursa(job #919559)

Utilizator apopeid13Apopeid Alejandro apopeid13 Data 19 martie 2013 18:50:16
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 kb
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <set>
#include <queue>
#define pii pair <int,int>
#define x first
#define y second
#define NMAX 100005
#define LMAX (1<<16)
using namespace std;
int t,n,m,rez,poz;
pii A[NMAX],B[NMAX];
char buff[LMAX];
int get_nr()
{
    int x=0;
    while (buff[poz]<'0' || buff[poz]>'9')
        if (++poz==LMAX)
            fread(buff,1,LMAX,stdin),poz=0;
    while (buff[poz]>='0' && buff[poz]<='9')
    {
       x=x*10+buff[poz]-'0';
       if (++poz==LMAX)
            fread(buff,1,LMAX,stdin),poz=0;
    }
    return x;
}
void read()
{
    n=get_nr(); m=get_nr();
    int i;
    for (i=1; i<=n; i++)
        A[i].x=get_nr(),A[i].y=get_nr();
    for (i=1; i<=m; i++)
        B[i].x=get_nr(),B[i].y=get_nr();
}
inline int max(int x,int y)
{
    return x>y ? x : y;
}
void solve()
{
    sort(A+1,A+n+1);
    sort(B+1,B+m+1);
    rez=0;
    int i,p=m+1,curr=-1,best=-1;
    for (i=n; i>=1; i--)
    {
        while (p-1>0 && B[p-1].x>=A[i].x)
            best=max(best,B[--p].y);
        if (A[i].y>curr)
        {
            curr=best;
            rez++;
        }
    }
}
int main()
{
    freopen("hvrays.in","r",stdin);
    freopen("hvrays.out","w",stdout);
    fread(buff,1,LMAX,stdin);
    t=get_nr();
    while (t--)
    {
        read();
        solve();
        printf("%d\n",rez);
    }
    return 0;
}