Cod sursa(job #74607)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 26 iulie 2007 18:16:58
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.53 kb
#include<stdio.h>
long int xmin[33000],xmax[33000],ymin[33000],ymax[33000],*lx[33000],*ly[33000],nr[33000],
n,i,aux,m,xx1,yy1,xx2,yy2,sol;
void heap(long int ic,long int nc,long int *l1,long int *l2);
void swap(long int i1,long int i2,long int *l1,long int *l2);
void apelx(long int ia);
void apely(long int ia);
long int cont(long int ic);
int inclus(long int ic);
int disjunct(long int ic);
int main()
{
	FILE *f,*g;
	f=fopen("zoo.in","r");
	g=fopen("zoo.out","w");
	fscanf(f,"%ld",&n);
	lx[1]=new long int [n+2];
	ly[1]=new long int [n+2];
	nr[1]=n;
	for(i=1;i<=n;i++)
	{ fscanf(f,"%ld%ld",&lx[1][i],&ly[1][i]);}
	for(i=n/2;i>=1;i--)
	 heap(i,n,lx[1],ly[1]);
	for(i=n;i>=1;i--)
	{ swap(1,i,lx[1],ly[1]);heap(1,i-1,lx[1],ly[1]);}
	apelx(1);
	fscanf(f,"%ld",&m);
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%ld%ld%ld%ld",&xx1,&yy1,&xx2,&yy2);
		sol=cont(1);
		fprintf(g,"%ld\n",sol);
	}
	fcloseall();
	return 0;
}
void swap(long int i1,long int i2,long int *l1,long int *l2)
{
	aux=l1[i1];l1[i1]=l1[i2];l1[i2]=aux;
	aux=l2[i1];l2[i1]=l2[i2];l2[i2]=aux;
}
void heap(long int ic,long int nc,long int *l1,long int *l2)
{
	long int is,is1;
	is=2*ic;
	is1=2*ic+1;
	if(is>nc) return;
	if(is<nc) if(l1[is]<l1[is1]) is=is1;
	if(l1[ic]<l1[is]){swap(is,ic,l1,l2);heap(is,nc,l1,l2);}
}
void apelx(long int ia)
{
	long int na,ii,is,id,ns,nd;
	na=nr[ia];
	if(na==1)
	{ ymin[ia]=ly[ia][1];
	  ymax[ia]=ly[ia][1];
	  xmin[ia]=lx[ia][1];
	  xmax[ia]=lx[ia][1];
	  delete lx[ia];
	  delete ly[ia];
	  return;
	}
	xmin[ia]=lx[ia][1];
	xmax[ia]=lx[ia][na];
	for(ii=na/2;ii>=1;ii--)
	 heap(ii,na,ly[ia],lx[ia]);
	for(ii=na;ii>=1;ii--)
	{ swap(1,ii,ly[ia],lx[ia]);heap(1,ii-1,ly[ia],lx[ia]);}
	ymin[ia]=ly[ia][1];
	ymax[ia]=ly[ia][na];
	is=2*ia;id=2*ia+1;
	nr[is]=na/2;
	nr[id]=na-nr[is];
	ns=nr[is];
	lx[is]=new long int [ns+2];
	ly[is]=new long int [ns+2];
	for(ii=1;ii<=ns;ii++)
	{ lx[is][ii]=lx[ia][ii];
	  ly[is][ii]=ly[ia][ii];
	}
	nd=nr[id];
	lx[id]=new long int [nd+2];
	ly[id]=new long int [nd+2];
	for(ii=1;ii<=nd;ii++)
	{ lx[id][ii]=lx[ia][ii+ns];
	  ly[id][ii]=ly[ia][ii+ns];
	}
	delete lx[ia];
	delete ly[ia];
	apely(is);
	apely(id);
}
void apely(long int ia)
{
	long int na,ii,is,id,ns,nd;
	na=nr[ia];
	if(na==1)
	{ ymin[ia]=ly[ia][1];
	  ymax[ia]=ly[ia][1];
	  xmin[ia]=lx[ia][1];
	  xmax[ia]=lx[ia][1];
	  delete lx[ia];
	  delete ly[ia];
	  return;
	}
	ymin[ia]=ly[ia][1];
	ymax[ia]=ly[ia][na];
	for(ii=na/2;ii>=1;ii--)
	 heap(ii,na,lx[ia],ly[ia]);
	for(ii=na;ii>=1;ii--)
	{ swap(1,ii,lx[ia],ly[ia]);heap(1,ii-1,lx[ia],ly[ia]);}
	xmin[ia]=lx[ia][1];
	xmax[ia]=lx[ia][na];
	is=2*ia;id=2*ia+1;
	nr[is]=na/2;
	nr[id]=na-nr[is];
	ns=nr[is];
	lx[is]=new long int [ns+2];
	ly[is]=new long int [ns+2];
	for(ii=1;ii<=ns;ii++)
	{ lx[is][ii]=lx[ia][ii];
	  ly[is][ii]=ly[ia][ii];
	}
	nd=nr[id];
	lx[id]=new long int [nd+2];
	ly[id]=new long int [nd+2];
	for(ii=1;ii<=nd;ii++)
	{ lx[id][ii]=lx[ia][ii+ns];
	  ly[id][ii]=ly[ia][ii+ns];
	}
	delete lx[ia];
	delete ly[ia];
	apelx(is);
	apelx(id);
}
long int cont(long int ic)
{
	long int is,id,ss,sd,ssol;
	if(inclus(ic)) return nr[ic];
	if(disjunct(ic)) return 0;
	is=2*ic;id=2*ic+1;
	ss=cont(is);sd=cont(id);
	ssol=ss+sd;
	return ssol;
}
int inclus(long int ic)
{
	if(xmin[ic]>=xx1)
	 if(xmax[ic]<=xx2)
	  if(ymin[ic]>=yy1)
	   if(ymax[ic]<=yy2)
	    return 1;
	return 0;
}
int disjunct(long int ic)
{
	if(xx1>xmax[ic]) return 1;
	if(xx2<xmin[ic]) return 1;
	if(yy1>ymax[ic]) return 1;
	if(yy2<ymin[ic]) return 1;
	return 0;
}