Cod sursa(job #181066)

Utilizator savimSerban Andrei Stan savim Data 17 aprilie 2008 20:45:38
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#include <algorithm>
#define maxl 100010
using namespace std;

int i,j,k,n,t,H,V,val;
int h[maxl][2],v[maxl][2];
int p[maxl],q[maxl];
char cit[30];

int cmp(int x, int y)
{
    return h[x][1]<h[y][1];    
}
int cmp2(int x, int y)
{
    return v[x][1]<v[y][1];
}
int main()
{
    freopen("hvrays.in","r",stdin);
    freopen("hvrays.out","w",stdout);
    
    scanf("%d",&t);
    while (t>0)
    {
        t--;
        scanf("%d %d\n",&H,&V);
        for (i=1; i<=H; i++)
        {
            fgets(cit,25,stdin);
            j=0;h[i][0]=0;h[i][1]=0;
            while (cit[j]!=' ')
            {
                h[i][0]=h[i][0]*10+cit[j]-48;
                j++;
            }
            j++;k=strlen(cit)-1;
            while (j<k)
            {
                h[i][1]=h[i][1]*10+cit[j]-48;
                j++;
            }
            p[i]=i;
        }

        for (i=1; i<=V; i++)
        {
            fgets(cit,25,stdin);
            j=0;v[i][0]=0;v[i][1]=0;
            while (cit[j]!=' ')
            {
                v[i][0]=v[i][0]*10+cit[j]-48;
                j++;
            }
            j++;k=strlen(cit)-1;
            while (j<k)
            {
                v[i][1]=v[i][1]*10+cit[j]-48;
                j++;
            }
            q[i]=i;
        }
        
        sort(p+1,p+H+1,cmp);
        sort(q+1,q+V+1,cmp2);
        
        j=V;k=0;val=0;
        for (i=H; i>=1; i--)
        if (h[p[i]][0]>=val)
        {
            k++;
            while (v[q[j]][1]>=h[p[i]][1] && j>0)
            {
                  if (v[q[j]][0]>val) val=v[q[j]][0];
                  j--;
            }
        }

        printf("%d\n",k);
    }
    
    return 0;    
}