Cod sursa(job #1074472)

Utilizator andreiiiiPopa Andrei andreiiii Data 7 ianuarie 2014 18:11:22
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <algorithm>
#include <cstdio>
#define PII pair<int, int>
#define x first
#define y second

using namespace std;

const int N=100002, INF=50000003;

PII a[N], b[N];

bool comp(PII a, PII b)
{
    return a.y<b.y;
}

int main()
{
    freopen("hvrays.in", "r", stdin);
    freopen("hvrays.out", "w", stdout);
    int t, n, m, i, j, sol, x;
    scanf("%d", &t);
    a[0].x=INF;
    a[0].y=-1;
    while(t--)
    {
        scanf("%d%d", &n, &m);
        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);
        sort(a+1, a+n+1, comp);
        sort(b+1, b+m+1, comp);
        sol=0;
        for(i=1, j=1, x=0;i<=m;i++)
        {
            if(a[x].x<=b[i].x) continue;
            sol++;
            for(;j<=n&&a[j].y<=b[i].y;j++)
            {
                if(a[j].x<a[x].x) x=j;
            }
        }
        printf("%d\n", sol);
    }
}