Cod sursa(job #645051)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 8 decembrie 2011 10:14:58
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

#define NMAX 17000
#define x first
#define y second
#define pb push_back
#define mp make_pair

using namespace std;

int N, Q, i, x1, y1, x2, y2, XSt, XDr, PX[NMAX];
pair< int, int > Puncte[NMAX];
vector< int > ArbY[(NMAX<<1)];

inline void BUILD( int Nod, int St, int Dr )
{
	if( St == Dr )
        ArbY[ Nod ].resize( 1, Puncte[St].y );

	else
	{
		int M = St + ((Dr-St)>>1);

		BUILD( (Nod<<1), St, M );
		BUILD( ((Nod<<1)|1), M + 1, Dr );

		ArbY[ Nod ].resize( ArbY[ (Nod<<1) ].size() + ArbY[ ((Nod<<1)|1) ].size() );
		merge( ArbY[ (Nod<<1) ].begin(), ArbY[ (Nod<<1) ].end(), ArbY[ ((Nod<<1)|1) ].begin(), ArbY[ ((Nod<<1)|1) ].end(), ArbY[ Nod ].begin() );
	}
}

inline int QUERY( int Nod, int St, int Dr, int XA, int XB, int YMIN, int YMAX )
{
	if( XA <= St && Dr <= XB )
        return (int)( upper_bound( ArbY[ Nod ].begin(), ArbY[ Nod ].end(), YMAX ) - lower_bound( ArbY[ Nod ].begin(), ArbY[ Nod ].end(), YMIN ) );
		
	else if( St == Dr ) return 0;
	else if( St < Dr )
	{
		int M = St + ((Dr-St)>>1);
		int Rez = 0;
		
		if( XA <= M )
            Rez += QUERY( (Nod<<1), St, M, XA, XB, YMIN, YMAX );
		if( XB > M )
            Rez += QUERY( ((Nod<<1)|1), M + 1, Dr, XA, XB, YMIN, YMAX );
		
		return Rez;
	}
}

int main()
{
	freopen("zoo.in", "r", stdin);
	freopen("zoo.out", "w", stdout);

	memset( ArbY, 0, sizeof(ArbY) );

	scanf("%d", &N);
	for( i = 1; i <= N; ++i )
	{
		scanf("%d%d", &Puncte[i].x, &Puncte[i].y );
		PX[i] = Puncte[i].x;
	}
	sort( Puncte + 1, Puncte + N + 1 );
	sort( PX + 1, PX + N + 1 );

	BUILD( 1, 1, N );

	scanf("%d", &Q);
	for( ; Q--; )
	{
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2 );
		XSt = (int)(lower_bound( PX + 1, PX + N + 1, x1 ) - PX);
		XDr = (int)(upper_bound( PX + 1, PX + N + 1, x2 ) - PX);
		--XDr;
		
		if( XSt > XDr )
		{
			printf("0\n");
			continue;
		}
		printf("%d\n", QUERY( 1, 1, N, XSt, XDr, y1, y2 ) );
	}

	return 0;
}