Cod sursa(job #843378)

Utilizator mariacMaria Constantin mariac Data 27 decembrie 2012 21:29:19
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 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];
int 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-1] == 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;
	int n1,m1;
	n1=arb[2*nod].size();
	m1=arb[2*nod+1].size();
	while(i < n1  &&  j < m1 )
	
		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 < n1)
    {
		arb[nod].push_back(arb[2*nod][i]);
		i++;
	}
	while(j < m1)
	{
		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;
}