Cod sursa(job #204460)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 24 august 2008 12:49:46
Problema Hvrays Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.54 kb
#include<stdio.h>
#define N 100002
#define L long
L t,a[N],b[N],c[N],d[N];
void readd(),solve(),hh(L ic,L nc),sh(L i1,L i2),hv(L ic,L nc),sv(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 cnt,n,h,v,i,j,bx,po,pv;
  scanf("%ld%ld",&h,&v);
  for(i=1;i<=h;i++)scanf("%ld%ld",&a[i],&b[i]);
  for(i=h/2;i>=1;i--)hh(i,h);
  for(i=h;i>=1;i--){sh(1,i);hh(1,i-1);}
  i=1;
  for(j=1;j<=h;j++)
  { if(a[j]<=a[i])continue;
    if(b[j]==b[i]){a[i]=a[j];continue;}
    i++;a[i]=a[j];b[i]=b[j];
  }
  h=i;
  //am redus la situatia in care
  //bh[1]>bh[2]>bh[3]>...>bh[h]
  //ah[1]<ah[2]<ah[3]<...<ah[h]
  for(i=1;i<=v;i++)scanf("%ld%ld",&c[i],&d[i]);
  for(i=v/2;i>=1;i--)hv(i,v);
  for(i=v;i>=1;i--){sv(1,i);hv(1,i-1);}
  bx=-1;po=1;pv=1;cnt=0;
  while(po<=h)
  { cnt++;
    while(d[pv]<=b[po])
     { if(c[pv]>bx)bx=c[pv];
       pv++;
     }
    while(po<=h&&a[po]<=bx)
     po++;
  }

  printf("%ld\n",cnt);
}
void hh(L ic,L nc)
{ L is=ic<<1;
  if(is>nc)return;
  if(is<nc)if(b[is+1]<b[is])is++;
  if(b[is]<b[ic]){sh(is,ic);hh(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;
}
void hv(L ic,L nc)
{ L is=ic<<1;
  if(is>nc)return;
  if(is<nc)if(d[is+1]<d[is])is++;
  if(d[is]<d[ic]){sv(is,ic);hv(is,nc);}
}
void sv(L i1,L i2)
{ L aux=c[i1];c[i1]=c[i2];c[i2]=aux;
    aux=d[i1];d[i1]=d[i2];d[i2]=aux;
}