Cod sursa(job #814777)

Utilizator radustn92Radu Stancu radustn92 Data 16 noiembrie 2012 03:06:08
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <cstdio>
#include <algorithm>
#include <set>
#include <queue>
#define pii pair <int,int>
#define x first
#define y second
#define NMAX 100005
using namespace std;
int t,n,m,rez;
pii A[NMAX],B[NMAX];
priority_queue <int> Q,Q2;
void read()
{
    scanf("%d%d",&n,&m);
    int i;
    for (i=1; i<=n; i++)
        scanf("%d%d",&A[i].x,&A[i].y);
    for (i=1; i<=m; i++)
        scanf("%d%d",&B[i].x,&B[i].y);
}
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);
    Q=Q2; rez=0;
    int i,p=m+1,best=-1;
    for (i=n; i>=1; i--)
    {
        while (p-1>0 && B[p-1].x>=A[i].x)
            Q.push(B[--p].y);
        if (A[i].y>best)
        {
            best=Q.top();
            Q.pop(); rez++;
        }
    }
}
int main()
{
    freopen("hvrays.in","r",stdin);
    freopen("hvrays.out","w",stdout);
    scanf("%d",&t);
    while (t--)
    {
        read();
        solve();
        printf("%d\n",rez);
    }
    return 0;
}