Cod sursa(job #42194)

Utilizator pocaituDavid si Goliat pocaitu Data 28 martie 2007 22:45:36
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.83 kb
#include<stdio.h>
#include<alloc.h>
#include<fstream.h>
#define nmax 63000
#define nrmax 230000
#define nodmax 326000
long n,val[nodmax],*p[nodmax],m,A[nrmax],B[nrmax],d[2][nrmax],y[16001],x[16001],x1[100001],x2[100001],y1[100001],y2[100001];
void citire_hash();




void add(long nod,long st,long dr,long x,long y)
{long mij;
 if(st>=x&&dr<=x)
	{
	val[nod]++;
	p[nod]=(long*) realloc(p[nod],(val[nod]+1)*sizeof(long));
	p[nod][val[nod]]=y;

	}

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


void sort(long v[16001],long n)
{long i,j;

 for(i=1;i<=n;i++)
   for(j=i+1;j<=n;j++)
	 if(v[i]>v[j])
	   {v[i]^=v[j];v[j]^=v[i];v[i]^=v[j];}
 }



void form_p(long nod,long st,long dr)
{long i,j,k;
 if(st==dr)
   {sort(p[nod],val[nod]);
	return;
	}
 form_p(2*nod,st,(st+dr)/2);
 form_p(2*nod+1,(st+dr)/2+1,dr);
 for(k=1,i=j=1;k<=val[2*nod]+val[2*nod+1];k++)
   if(p[2*nod][i]<p[2*nod+1][j]&&i<=val[2*nod]||j>val[2*nod+1])
	  p[nod][k]=p[2*nod][i++];
   else
	  p[nod][k]=p[2*nod+1][j++];
 }


long cautare(long nod,long x)
{long ls=1,ld=val[nod],mij;

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



long inter(long nod,long st,long dr,long x1,long x2,long y1,long y2)
{long d1,d2,s=0,mij;
 if(st>=x1&&dr<=x2)
	{d1=cautare(nod,y1);
	 if(d1<0) d1=1;
	 while(d1>1&&p[nod][d1-1]==p[nod][d1]) d1--;
	 d2=cautare(nod,y2);
	 if(d2>val[nod]) d2=val[nod];
	 while(d2<val[nod]&&p[nod][d2+1]==p[nod][d2]) d2++;
	 if(d2) return d2-d1+1;
	  else return 0;
	 }
  else
   {mij=(st+dr)/2;
	if(x1<=mij) s+=inter(2*nod,st,mij,x1,x2,y1,y2);
	if(x2>mij) s+=inter(2*nod+1,mij+1,dr,x1,x2,y1,y2);
	return s;
	}
  }







int main()
{long d,i;
 freopen("zoo.in","r",stdin);
 //aloc memorie dinamic pt p
 for(i=1;i<=nodmax-3;i++)
   p[i]=(long *) realloc(p[i],sizeof(long));
 citire_hash();
 for(i=1;i<=n;i++)
  add(1,0,nmax,x[i],y[i]);

 form_p(1,0,nmax);

 //freopen("zoo.out","w",stdout);
 ofstream g("zoo.out");
 for(i=1;i<=m;i++)
  {d=inter(1,0,nmax,x1[i],x2[i],y1[i],y2[i]);
   g<<d<<'\n';
   }
 g.close();
 return 0;

 }
long cauta(int a,int n,int x)
{long ls=1,ld=n,mij;

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


 }



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 && A[i] < A[j]))
			B[k++] = A[i++];
		else
			B[k++] = A[j++];
	for (k = l; k <= r; k++) A[k] = B[k];
}


void citire_hash()
{long i,j,nn1,nn2;
 scanf("%ld",&n);

 for(i=1;i<=n;i++)
  {scanf("%ld%ld",&x[i],&y[i]);
   d[0][i]=x[i];
   d[1][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]);
   d[0][n+2*(i/2)+i%2]=x1[i];
   d[0][n+2*(i/2)+i%2+1]=x2[i];
   d[1][n+2*(i/2)+i%2]=y1[i];
   d[1][n+2*(i/2)+i%2+1]=y2[i];
   }
 memcpy(A,d[0],sizeof(A));
 merge_sort(1,n+m);
 memcpy(d[0],A,sizeof(A));
 for(i=1,nn1=0;i<=n+m;i++)
  {d[0][++nn1]=d[0][i];
   while(d[0][i]==d[0][i+1]) i++;
   }

 memcpy(d[1],A,sizeof(A));
 merge_sort(1,n+m);
 memcpy(d[1],A,sizeof(A));


  for(i=1,nn2=0;i<=n+m;i++)
  {d[1][++nn2]=d[1][i];
   while(d[1][i]==d[1][i+1]) i++;
   }

 for(i=1;i<=n;i++)
   {
   x[i]=cauta(0,nn1,x[i])-1;
   y[i]=cauta(1,nn2,y[i])-1;
   }
 for(i=1;i<=m;i++)
   {
   x1[i]=cauta(0,nn1,x1[i])-1;
   y1[i]=cauta(1,nn2,y1[i])-1;
   x2[i]=cauta(0,nn1,x2[i])-1;
   y2[i]=cauta(1,nn2,y2[i])-1;
   }
 }