Pagini recente » Cod sursa (job #3130562) | Cod sursa (job #1232124) | Cod sursa (job #2582275) | Cod sursa (job #43518) | Cod sursa (job #203247)
Cod sursa(job #203247)
#include <stdio.h>
#define FIN "hvrays.in"
#define FOUT "hvrays.out"
#define NMAX 110100
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,mx,p;
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;
++i;
--j;
}
}
while (i<=j);
if (li<j) quicksort1(li,j);
if (i<ls) quicksort1(i,ls);
}
void quicksort3(long int li, long int ls)
{
i=li;
j=ls;
mij=v2[(li+ls)>>1];
do
{
while (v2[j]>mij) --j;
while (v2[i]<mij) ++i;
if (i<=j)
{
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 quicksort4(long int li, long int ls)
{
i=li;
j=ls;
mij=x2[(li+ls)>>1];
do
{
while (x2[j]>mij) --j;
while (x2[i]<mij) ++i;
if (i<=j)
{
aux=x2[i];
x2[i]=x2[j];
x2[j]=aux;
++i;
--j;
}
}
while (i<=j);
if (li<j) quicksort1(li,j);
if (i<ls) quicksort1(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(1,n);
quicksort2(1,m);
quicksort3(1,n);
quicksort4(1,m);
i=0;
j=0;
REZ=0;
x=-1;
for (i=1,j=1;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=1;i<=n;++i)
scanf("%ld %ld", &v1[i], &v2[i]);
for (i=1;i<=m;++i)
scanf("%ld %ld", &x1[i], &x2[i]);
solve();
--T;
}
}
int main()
{
read();
return 0;
}