Cod sursa(job #1074482)

Utilizator andreiiiiPopa Andrei andreiiii Data 7 ianuarie 2014 18:16:00
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 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;
    char cit[40], *p;
    scanf("%d\n", &t);
    a[0].x=INF;
    a[0].y=-1;
    while(t--)
    {
        scanf("%d %d\n", &n, &m);
        for(i=1;i<=n;i++)
        {
            a[i].x=a[i].y=0;
            fgets(cit, 40, stdin);
            for(p=cit;*p>='0'&&*p<='9';p++) a[i].x=10*a[i].x+*p-'0'; p++;
            for(;*p>='0'&&*p<='9';p++) a[i].y=10*a[i].y+*p-'0'; p++;
        }
        for(i=1;i<=m;i++)
        {
            b[i].x=b[i].y=0;
            fgets(cit, 40, stdin);
            for(p=cit;*p>='0'&&*p<='9';p++) b[i].x=10*b[i].x+*p-'0'; p++;
            for(;*p>='0'&&*p<='9';p++) b[i].y=10*b[i].y+*p-'0'; p++;
        }
        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);
    }
}