Cod sursa(job #204469)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 24 august 2008 14:37:51
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<stdio.h>
#define N 200001
long t,o,v,n,i,cnt,bc,bn,p[N],a[N],b[N],ord(long i1,long i2);
void readd(),solve(),hd(long ic,long nc),sh(long i1,long 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()
{ scanf("%ld%ld",&o,&v);n=0;
  for(i=1;i<=o;i++){p[++n]=0;scanf("%ld%ld",&a[i],&b[i]);}
  for(i=1;i<=v;i++){p[++n]=1;scanf("%ld%ld",&a[i],&b[i]);}
  for(i=n/2;i;i--)hd(i,n);
  for(i=n;i;i--){sh(1,i);hd(1,i-1);}
  bc=bn=-1;cnt=0;
  for(i=1;i<=n;i++)
  { if(p[i]){bn=(bn>a[i])?bn:a[i];}
    else if(a[i]>bc){cnt++;bc=bn;}
  }
  printf("%ld\n",cnt);
}
void hd(long ic,long nc)
{
	long is=ic<<1;
	if(is>nc)return;
	if(is<nc)if(ord(is,is+1))is++;
	if(ord(ic,is)){sh(is,ic);hd(is,nc);}
}
void sh(long i1,long i2)
{
	long aux=a[i1];a[i1]=a[i2];a[i2]=aux;
	     aux=b[i1];b[i1]=b[i2];b[i2]=aux;
	     aux=b[i1];b[i1]=b[i2];b[i2]=aux;
}
long ord(long i1,long i2)
{  if(b[i1]<b[i2])return 1;
   if(b[i1]>b[i2])return 0;
   if(p[i1]<p[i2])return 1;
   if(p[i1]>p[i2])return 0;
   if(a[i1]<a[i2])return 1;
   return 0;
}