Cod sursa(job #42478)

Utilizator pocaituDavid si Goliat pocaitu Data 29 martie 2007 11:18:09
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.42 kb
#include<stdio.h>
#include<alloc.h>
#define nodmax 50009
#define nmax 16001
#define mm 100001
void citire();void merge_sort(int,int);void form_tree();void inter_tree();
int n;
long m,*p[nodmax],b1[nmax],b2[nmax],x[nmax],y[nmax],x1[mm],x2[mm],y1[mm],y2[mm];

int main()
{citire();
 merge_sort(1,n);
 form_tree();
 inter_tree();
 return 0;
 }

int caut1(long a,int nod)
{int ls=1,ld=p[nod][0],mij;

 while(ls<=ld)
  {mij=(ls+ld)/2;
   if(p[nod][mij]<a)
	 ls=mij+1;
   else if(p[nod][mij]>a)
	  ld=mij-1;
	else
	  return mij;
	}
 return ld+1;

 }



int inter(int nod,int st,int dr,int a,int b,long y1,long y2)
{int s=0,d,mij;
 if(st>=a&&dr<=b)
  {s=caut1(y1,nod);
   d=caut1(y2,nod);
   if(d>p[nod][0]||p[nod][d]>y2) d--;
   if(s==0||p[nod][s]<y1) s++;
   while(p[nod][s-1]>=y1&&s-1>0) s--;
   while(p[nod][d+1]<=y2&&d+1<=p[nod][0]) d++;
   return d-s+1;
   }
 else
   {mij=(st+dr)/2;
	if(a<=mij)
	   s+=inter(2*nod,st,mij,a,b,y1,y2);
	if(b>mij)
	   s+=inter(2*nod+1,mij+1,dr,a,b,y1,y2);
	 return s;
	 }
  }


int cautare(long a)
{
 int ls=1,ld=n,mij;
 while(ls<=ld)
  {mij=(ls+ld)/2;
   if(x[mij]<a)
	 ls=mij+1;
   else if(x[mij]>a)
	  ld=mij-1;
	else
	  return mij;
	}
 return ld+1;

 }

void inter_tree()
{int s,d;
 long i;
 freopen("zoo.out","w",stdout);
 for(i=1;i<=m;i++)

  {s=cautare(x1[i]);
   if(s<=0||x[s]>x1[i]) s++;
   //while(x[s]<x1[i]) s++;
   while(x[s-1]>=x1[i]&&s-1>0) s--;
   d=cautare(x2[i]);
   if(x[d]<x2[i]||d>n) d--;
   while(x[d+1]<=x2[i]&&d+1<=n) d++;

   d=inter(1,1,n,s,d,y1[i],y2[i]);
   printf("%d\n",d);

   }
 fclose(stdout);
 }










void sort(int nod,int st,int dr)
{int k,i,j;
 p[nod]=(long*) realloc(p[nod],(p[nod][0]+2)*sizeof(long));

 if(st==dr)
	return;
 sort(2*nod,st,(st+dr)/2);
 sort(2*nod+1,(st+dr)/2+1,dr);

 for(k=i=j=1;k<=p[nod][0];)
  if(i<=p[2*nod][0]&&p[2*nod][i]<p[2*nod+1][j]||j>p[2*nod+1][0])
	p[nod][k++]=p[2*nod][i++];
  else
	p[nod][k++]=p[2*nod+1][j++];
 }

void add(int nod,int st,int dr,int x,long y)
{int mij;

 if(st==dr)
   {p[nod]=(long*) realloc(p[nod],2*sizeof(long));
   p[nod][0]=1;
   p[nod][1]=y;
   }
 else
  {//p[nod]=(long*)realloc(p[nod],sizeof(long));
   mij=(st+dr)/2;
   p[nod][0]++;
   if(x<=mij) add(2*nod,st,mij,x,y);
   if(x>mij) add(2*nod+1,mij+1,dr,x,y);
   }
 }



void form_tree()
{int i;
 for(i=1;i<=nodmax-1;i++)
   {
   p[i]=(long*) realloc(p[i],sizeof(long));
   p[i][0]=0;
   }
 for(i=1;i<=n;i++)
  add(1,1,n,i,y[i]);
 sort(1,1,n);

 }

























void merge_sort(int l,int r)
{
 int m=(l+r)/2,i,j,k;
 if(l==r) return;
 merge_sort(l,m);
 merge_sort(m+1,r);
 for(k=l,i=l,j=m+1;k<=r;)
  if(x[i]<x[j]&&i<=m||j>=r)
	{b1[k]=y[i];
	 b2[k++]=x[i++];
	 }
  else
	 {b1[k]=y[j];
	  b2[k++]=x[j++];
	  }
 for(k=l;k<=r;k++)
  {
   x[k]=b2[k];
   y[k]=b1[k];
   }
 }
 /*
void merge_sort(int l, int r)
{
	int m = (l + r) >> 1, i, j, k;
	if (l == r) return;
	merge_sort(l, m);
	merge_sort(m + 1, r);
	for (i=l, j=m+1, k=l; i<=m || j<=r; )
		if (j > r || (i <= m && x[i] < x[j]))
			B[k++] = A[i++];
		else
			B[k++] = A[j++];
	for (k = l; k <= r; k++) A[k] = B[k];
}

  */




void citire()
{int i;
 freopen("zoo.in","r",stdin);
 scanf("%d",&n);
 for(i=1;i<=n;i++)
  scanf("%ld%ld",&x[i],&y[i]);
 scanf("%ld",&m);
 for(i=1;i<=m;i++)
  scanf("%ld%ld%ld%ld",&x1[i],&y1[i],&x2[i],&y2[i]);
 }