Cod sursa(job #374256)

Utilizator Darth_NiculusIvan Nicolae Darth_Niculus Data 16 decembrie 2009 15:39:18
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
/* Ivan Nicolae - Hvrays */
#include <stdio.h>
#include <stdlib.h>

#define NMAX 200001
#define _fin  "hvrays.in"
#define _fout "hvrays.out"

long i,j,n,t,h,v;
long x[NMAX],y[NMAX],tp[NMAX];

void Quick(long li, long ls)
{
 long i=li,j=ls,xx=x[(li+ls)/2],yy;
 
 while (i<=j)
      {
       while (x[i]>xx) i++;
       while (x[j]<xx) j--;
       if (i<=j)
         {
          yy=x[i]; x[i]=x[j]; x[j]=yy;
          yy=y[i]; y[i]=y[j]; y[j]=yy;
          yy=tp[i]; tp[i]=tp[j]; tp[j]=yy;
          i++; j--;
         }
      }
 if (i<=ls) Quick(i,ls);
 if (li<=j) Quick(li,j);
}

int main()
{
 freopen(_fin,"r",stdin);
 freopen(_fout,"w",stdout);
 
 scanf("%ld",&t);
 while (t)
      {
       t--;
       scanf("%ld%ld",&h,&v);
       for (i=1;i<=h;i++)
          {
           scanf("%ld%ld",&x[i],&y[i]);
           tp[i]=1;
          }
       for (i=h+1;i<=h+v;i++)
          {
           scanf("%ld%ld",&x[i],&y[i]);
           tp[i]=2;
          }
       n=h+v;
       
       Quick(1,n);
       
       long max=0,maxx=0,nr=0;
       
       for (i=n;i>=1;i--)
          if (tp[i]==2 && y[i]>maxx)
            maxx=y[i];
            else if (tp[i]==1 && y[i]>max)
                   {
                    nr++;
                    max=maxx;
                   }
       printf("%ld\n",nr);
      }
 
 fclose(stdin);
 fclose(stdout);
 return 0;
}