Cod sursa(job #426069)

Utilizator marius135Dumitran Adrian Marius marius135 Data 26 martie 2010 13:26:10
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.57 kb
#include<stdio.h>
#include<vector>
#define maxn 32*1024

using namespace std;

struct punct{ int x,y;};
punct p[ maxn ];

vector < int > PY[ maxn];
int ST[ maxn], DR[maxn], n;
int X1, Y1, X2, Y2;

int cmppunct( const void *a, const void *b)
{
	return (*( punct *) a).x - (* ( punct *) b).x;
}


void interclasare( int where, int x1, int x2)
{
	int size1 = PY[x1].size(), size2 = PY[x2].size();
	int st1 = 0, st2 = 0;
	for( int i = 0; i < size1 + size2; ++i)
	{
		if( st1 == size1 )
			{PY[ where ].push_back( PY[x2][ st2++]);continue;}
		if( st2 == size2)
			{PY[ where ].push_back( PY[x1][ st1++]);continue;}
		if( PY[x2][st2] < PY[x1][st1])
			{PY[ where ].push_back( PY[x2][ st2++]);continue;}
		PY[ where ].push_back( PY[x1][ st1++]);
	}
	
}

void create( int nod, int left, int right)
{
	if( left == right)
	{
		ST[ nod ] = p[left].x; DR[ nod ] = p[right].x; 
		PY[nod].push_back( p[right].y);
		return ;
	}
	create( nod * 2, left, (left + right)>>1 );
	create( nod * 2 + 1, (( left + right) >> 1) + 1, right);
	ST [ nod ] = ST[ nod * 2 ]; DR[ nod ] = DR[ nod * 2 + 1];
	interclasare( nod, nod * 2, nod * 2 + 1);
	
	/*printf("%d %d %d left %d right %d\n yeci:", nod, ST[nod], DR[nod], left, right);
	for( int i = 0 ; i < PY[nod].size(); ++i)
	{
		printf("%d ",PY[nod][i]);
	}
	printf("\n");*/
}

int cauta( int nod, int value)
{
	int left = 0, right = PY[ nod].size() - 1;
	while( left != right)
	{
		if( left == right -1 )
		{
			if( PY[nod][ left ] < value) return left;
			return right;
		}
		int mij = ( left + right)/2;
		if( PY[nod][ mij] > value)
		{
			right = mij; continue;
		}
		else left = mij ;
	}
	if( PY[nod][ left ] >= value) return left-1;
	return left;
}

int answery( int nod )
{
	return cauta( nod, Y2) - cauta( nod , Y1 - 1);
}

int answer( int nod, int left, int right)
{
	if( left >= X1 && right <= X2)
		{ int rez = answery( nod ); printf("%d %d %d %d\n",nod,left,right,rez); return rez;}
	if( left > X2 || right < X1)
		return 0;
	//printf("%d %d %d\n",nod,left,right);
	return answer( nod * 2, left, (left + right)>>1 ) + answer( nod * 2 + 1, (( left + right) >> 1) + 1, right);
	
	
	
}
int main()
{
	freopen("zoo.in","r",stdin);
	//freopen("zoo.out","w",stdout);
	
	scanf("%d",&n);
	
	for( int i = 1; i <= n; ++i)
	{
		scanf("%d %d",&p[i].x,&p[i].y);
	}
	qsort(p+1, n, sizeof(p[0]), cmppunct);
	
	create( 1, 1, n);
	int m;
	scanf("%d",&m);
	
	for( int i = 1; i <= m; ++i)
	{
		
		scanf("%d %d %d %d",&X1, &Y1, &X2, &Y2);
		printf("%d\n",answer( 1, 1, n));
	}
	
	return 0;
}