Cod sursa(job #74606)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 26 iulie 2007 18:15:28
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.35 kb
#include<stdio.h>
struct nod{
long int ii1;
long int ii2;
long int xx1;
long int xx2;
long int yy1;
long int yy2;
long int *li;
nod *st;
nod *dr;
};
long int n,m,i,aux,xc1,xc2,yc1,yc2,sol,x[1600],y[1600],yo[1600],ind[1600];
nod *ai;
void swapx(long int i1,long int i2);
void swapy(long int i1,long int i2);
void heapx(long int ic,long int nc);
void heapy(long int ic,long int nc);
void c1(long int ll,long int rr,nod *aa);
void c2(nod *aa);
long int num(nod *aa,long int xp1,long int xp2);
int main()
{
	FILE *f,*g;
	f=fopen("zoo.in","r");
	g=fopen("zoo.out","w");
	fscanf(f,"%ld",&n);
	for(i=1;i<=n;i++)
	{ fscanf(f,"%ld%ld",&x[i],&y[i]);}
	for(i=n/2;i>=1;i--)
	 heapx(i,n);
	for(i=n;i>=1;i--)
	{ swapx(1,i);heapx(1,i-1);}
	for(i=1;i<=n;i++)
	 { ind[i]=i;
	   yo[i]=y[i];
	 }
	for(i=n/2;i>=1;i--)
	 heapy(i,n);
	for(i=n;i>=1;i--)
	{ swapy(1,i);heapy(1,i-1);}
	ai=new nod;
	c1(1,n,ai);
	for(i=1;i<=n;i++)
	 ai->li[i]=ind[i];
	c2(ai);
	fscanf(f,"%ld",&m);
	for(i=1;i<=m;i++)
	{
		fscanf(f,"%ld%ld%ld",&xc1,&yc1,&xc2,&yc2);
		sol=num(ai,xc1,xc2);
		fprintf(g,"%ld\n",sol);
	}
	fprintf(g,"\n");
	fcloseall();
	return 0;
}
void swapx(long int i1,long int i2)
{
   aux=x[i1];x[i1]=x[i2];x[i2]=aux;
   aux=y[i1];y[i1]=y[i2];y[i2]=aux;
}
void swapy(long int i1,long int i2)
{
   aux=yo[i1];yo[i1]=yo[i2];yo[i2]=aux;
   aux=ind[i1];ind[i1]=ind[i2];ind[i2]=aux;
}
void heapx(long int ic,long int nc)
{
	int is,is1;
	is=2*ic;is1=2*ic+1;
	if(is>nc) return;
	if(is<nc) if(x[is]<x[is1]) is=is1;
	if(x[ic]<x[is]){ swapx(is,ic);heapx(is,nc);}
}
void heapy(long int ic,long int nc)
{
	int is,is1;
	is=2*ic;is1=2*ic+1;
	if(is>nc) return;
	if(is<nc) if(yo[is]<yo[is1]) is=is1;
	if(yo[ic]<yo[is]){ swapy(is,ic);heapy(is,nc);}
}
void c1(long int ll,long int rr,nod *aa)
{
	long int mm;
	aa->ii1=ll;
	aa->ii2=rr;
	aa->li=new long int [rr-ll+2];
	if(ll==rr) {aa->st=0;aa->dr=0;return;}
	mm=(ll+rr)/2;
	aa->st=new nod;
	aa->dr=new nod;
	c1(ll,mm,aa->st);
	c1(mm+1,rr,aa->dr);
}
void c2(nod *aa)
{
	long int mm,i2,is,id;
	aa->xx1=x[aa->ii1];
	aa->xx2=x[aa->ii2];
	aa->yy1=y[aa->li[1]];
	aa->yy2=y[aa->li[aa->ii2-aa->ii1+1]];
	mm=(aa->ii1+aa->ii2)/2;
        is=0;id=0;
	for(i2=aa->ii1;i2<=aa->ii2;i2++)
	{
	  if(aa->li[i2]<=mm)
	  {is++;aa->st->li[is]=aa->li[i2];}
	  else
	  {id++;aa->dr->li[id]=aa->li[i2];}
	}
}