Cod sursa(job #204457)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 24 august 2008 11:09:20
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include<stdio.h>
#define N 200002
#define L long
L t,a[N],b[N],p[N];
void readd(),solve(),hd(L ic,L nc),sh(L i1,L i2);
L ord(L i1,L i2);
int main()
{
	readd();
	for(;t;t--)solve();
	return 0;
}
void readd()
{
	freopen("hvrays.in","rt",stdin);
	freopen("hvrays.out","wt",stdout);
	scanf("%ld",&t);
}
void solve()
{ L l,r,c,n,h,v,i;
  scanf("%ld%ld",&h,&v);
  l=r=-1;
  c=n=0;
  for(;h;h--)
  { p[++n]=1;scanf("%ld%ld",&a[n],&b[n]);}
  for(;v;v--)
  { p[++n]=2;scanf("%ld%ld",&a[n],&b[n]);}
  for(i=n/2;i;i--)hd(i,n);
  for(i=n;i;i--){sh(1,i);hd(1,i-1);}
  for(;n;n--)
  { if(p[n]==2){ if(a[i]>r)r=a[i];continue;}
    if(a[n]<=l)continue;
    l=r;c++;
  }
  printf("%ld\n",c);
}
void hd(L ic,L nc)
{
	L is=ic<<1;
	if(is>nc)return;
	if(is<nc)if(ord(is,is+1))is++;
	if(ord(is,is)){sh(is,ic);hd(is,nc);}
}
void sh(L i1,L i2)
{ L aux=a[i1];a[i1]=a[i2];a[i2]=aux;
    aux=b[i1];b[i1]=b[i2];b[i2]=aux;
    aux=p[i1];p[i1]=p[i2];p[i2]=aux;
}
L ord(L i1,L i2)
{ if(b[i1]<b[i2])return 1;
  if(p[i1]<p[i2])return 1;
  return 0;
}