Cod sursa(job #833218)

Utilizator mariacMaria Constantin mariac Data 12 decembrie 2012 01:36:00
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.39 kb
#include<fstream>
#include<vector>

using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");


struct punct
{
	int x,y;
};
vector <int> arb[33000];
punct v[16002];
int p=1,n,mm;
int x1,y11,x2,y2;
punct inter[16002];
int norm[16002], k,nr;
void  interog(int nod,int st,int dr,int a,int b)
{if(st>=a&&dr<=b){
				int s,d,m;
			   s=0;
			   d=arb[nod].size()-1;
			   m=(s+d)/2;
			   while(s<=d&&arb[nod][m]!=y11)
				   {if(arb[nod][m]<y11)s=m+1;
					   else d=m-1;
				    m=(s+d)/2;}
				int a1,b1;
				while(m-1>=0&&arb[nod][m]==y11)m--;
			    if(s>d)a1=s;
				   else a1=m;
				s=0;
			   d=arb[nod].size()-1;
			   m=(s+d)/2;
			   while(s<=d&&arb[nod][m]!=y2)
				  { if(arb[nod][m]<y2)s=m+1;
					   else d=m-1;
				   m=(s+d)/2;}
				  while(m+1<arb[nod].size()&&arb[nod][m+1]==y2)m++;
			    if(s>d)b1=d;
				   else b1=m;
				
				if(b1-a1+1>0)nr+=b1-a1+1;
			}
   else {
		   int m;
		   m=(st+dr)/2;
		   if(a<=m)interog(nod*2,st,m,a,b);
		   if(b>m)interog(nod*2+1,m+1,dr,a,b);
   }
}
				
void cauta(){
	           int st,dr,m;
			   st=1;
			   dr=k;
			   m=(st+dr)/2;
			   while(st<=dr&&norm[m]!=x1)
				   {if(norm[m]<x1)st=m+1;
					   else dr=m-1;
				    m=(st+dr)/2;
				   }
				
				int a,b;
			    if(st>dr)a=st;
				   else a=m;
				 st=1;
			   dr=k;
			   m=(st+dr)/2;
			   while(st<=dr&&norm[m]!=x2)
				   {if(norm[m]<x2)st=m+1;
					   else dr=m-1;
				    m=(st+dr)/2;
				   }
				
			   if(st>dr)b=dr;
				   else b=m;
			   
			   if(a<=b)interog(1,1,k,a,b);

}


void intercl(int nod)
{
	int i,j;
	i=j=0;
	
	while(i<arb[2*nod].size()&&j<arb[2*nod+1].size())
	
		if(arb[2*nod][i]<arb[2*nod+1][j])
			{
				arb[nod].push_back(arb[2*nod][i]);
				i++;
		}
		else
			{
				arb[nod].push_back(arb[2*nod+1][j]);
				j++;
			}
		while(i<arb[2*nod].size())

			{arb[nod].push_back(arb[2*nod][i]);
				i++;
			}
		while(j<arb[2*nod+1].size())

			{
				arb[nod].push_back(arb[2*nod+1][j]);
				j++;
			}
		
		
}
void actualizare(int nod,int st,int dr)
{
	if(st==dr){	
				while(p<=n&&v[p].x==norm[st])
				   {  
					   arb[nod].push_back(v[p].y);
					   p++;
					}
			   }
	  else
	  {
		  int m;
		  m=(st+dr)/2;
		  actualizare(nod*2,st,m);
		  actualizare(nod*2+1,m+1,dr);
		  intercl(nod);
		  
	  }
}

void interclasare(int st,int m,int dr)
{
	int i,j;
	int k;
	k=st-1;
	i=st;
	j=m+1;
	while(i<=m&&j<=dr)
	
		if(v[i].x<v[j].x||v[i].x==v[j].x&&v[i].y<v[j].y)
			{
				inter[++k].x=v[i].x;
				inter[k].y=v[i].y;
				i++;
			}
		else
			{
				inter[++k].x=v[j].x;
				inter[k].y=v[j].y;
				j++;
			}
		while(i<=m)

			{
				inter[++k].x=v[i].x;
				inter[k].y=v[i].y;
				i++;
			}
		while(j<=dr)

			{
				inter[++k].x=v[j].x;
				inter[k].y=v[j].y;
				j++;
			}
		for(i=st;i<=dr;i++)
			{
				v[i].x=inter[i].x;
			    v[i].y=inter[i].y;
			}
		
}
	
void ms(int st,int dr)
{
	if(st<dr)
	{
		ms(st,(st+dr)/2);
		ms((st+dr)/2+1,dr);
		interclasare(st,(st+dr)/2,dr);
	}
		
}
int main()
{
	int i;
	fin>>n;
	for(i=1;i<=n;i++)
		{
			fin>>v[i].x;
			fin>>v[i].y;
			
		}
	ms(1,n);
	norm[1]=v[1].x;
	k=1;
	for(i=2;i<=n;i++)
		 if(v[i-1].x!=v[i].x)norm[++k]=v[i].x;
		
	actualizare(1,1,k);
	
	fin>>mm;
	
	for(i=1;i<=mm;i++)
	{
		fin>>x1>>y11>>x2>>y2;
		nr=0;
		cauta();
		fout<<nr<<"\n";
	}
	
	return 0;
}