Cod sursa(job #203178)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 14 august 2008 13:29:46
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <stdio.h>

#define FIN "hvrays.in"
#define FOUT "hvrays.out"
#define NMAX 100100

long int n,m;
long int v1[NMAX],v2[NMAX];
long int x1[NMAX],x2[NMAX];
int T;
long int i,j;
long int aux,mij;
long int REZ,x,nr;


void quicksort1(long int li, long int ls)
{

i=li;
j=ls;
mij=v1[(li+ls)>>1];

do
  {
   while (v1[j]>mij) --j;
   while (v1[i]<mij) ++i;
   if (i<=j)
      {
       aux=v1[i];
       v1[i]=v1[j];
       v1[j]=aux;
       aux=v2[i];
       v2[i]=v2[j];
       v2[j]=aux;
       ++i;
       --j;
	}
   }
while (i<=j);
if (li<j) quicksort1(li,j);
if (i<ls) quicksort1(i,ls);
}

void quicksort2(long int li, long int ls)
{

i=li;
j=ls;
mij=x1[(li+ls)>>1];

do
  {
   while (x1[j]>mij) --j;
   while (x1[i]<mij) ++i;
   if (i<=j)
      {
       aux=x1[i];
       x1[i]=x1[j];
       x1[j]=aux;
       aux=x2[i];
       x2[i]=x2[j];
       x2[j]=aux;
       ++i;
       --j;
	}
   }
while (i<=j);
if (li<j) quicksort2(li,j);
if (i<ls) quicksort2(i,ls);
}



void write()
{

printf("%ld\n", REZ);
}


long int max(long int a,long int b)
{
if (a>b)
   return a;
   else
   return b;

}


void solve()
{

quicksort1(0,n);
quicksort2(0,m);

i=0;
j=0;
REZ=0;
x=-1;
for (i=0,j=0;i<n && j<m;i++)
     {
     if (v2[i]>x)
	 {
	 REZ++;
	 while (j<m && v1[i]<=x1[j])
	 {
	       nr=max(nr,x2[j]);
	       j++;
	       }

	       }
	}
write();
}




void read()
{

freopen(FIN,"rt",stdin);
freopen(FOUT,"wt",stdout);

scanf("%d", &T);

while (T)
       {
	scanf("%ld %ld", &n, &m);

	for (i=0;i<n;++i)
	    scanf("%ld %ld", &v1[i], &v2[i]);

	for (i=0;i<m;++i)
	    scanf("%ld %ld", &x1[i], &x2[i]);

	    solve();
	    --T;
	    }
}


int main()
{
read();
return 0;
}