Cod sursa(job #91026)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 11 octombrie 2007 10:38:03
Problema Hvrays Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 100010

int n,m,sol,best,next;
int a[maxn],b[maxn],p[maxn],x[maxn],y[maxn],q[maxn];

int cmp(int i,int j)
{
    return (a[i]>a[j]) || ((a[i]==a[j]) && (b[i]<b[j]));
}

int cmp2(int i,int j)
{
    return x[i]>x[j];
}

int main()
{
    freopen("hvrays.in","r",stdin);
    freopen("hvrays.out","w",stdout);
    
    int i,j,T;
    scanf("%d ",&T);
    
    while (T>0)
    {
          scanf("%d %d ",&n,&m);
    
          for (i=1;i<=n;i++)
          {
              scanf("%d %d ",&a[i],&b[i]);
              p[i]=i;
          }
    
          for (i=1;i<=m;i++) 
          {
              scanf("%d %d ",&x[i],&y[i]);
              q[i]=i;
          }         
    
          sort(p+1,p+n+1,cmp);
          sort(q+1,q+m+1,cmp2);
          
          j=1;
          next=best=-1;
          sol=0;
          
          for (i=1;i<=n;i++)
          {
              for (;j<=m && x[q[j]]>=a[p[i]];j++)
                if (y[q[j]]>next) next=y[q[j]];
                
              if (b[p[i]]>best)
              {
                  sol++;
                  best=next;
              }
          }
          
          printf("%d\n",sol);
          T--;
    }
    
    return 0;
}