Cod sursa(job #203171)

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

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

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


void quicksort1(int li, 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(int li, 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("%d\n", REZ);
}


void solve()
{

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

i=0;
j=0;
REZ=0;
x=0;

while (i<n)
      {
       j=nr+1;
       while ((x2[j]>=v2[nr]) && j<=m)
	     {
	      if (x1[j]>x1[nr])
		 nr=j;

		 j++;
		 }
	       REZ++;
	       while ((v1[i]<=x1[nr]) && i<n)
		     i++;
		     }

write();
}




void read()
{

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

scanf("%d", &T);

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

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

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

	    solve();
	    --T;
	    }
}


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