Nu aveti permisiuni pentru a descarca fisierul grader_test9.in

Cod sursa(job #644987)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 7 decembrie 2011 22:23:20
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

#define NMAX 16005
#define x first
#define y second
#define xinv second
#define yinv first
#define pb push_back
#define mp make_pair

using namespace std;

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

inline void UPDATE( int Nod, int St, int Dr, int Pos, pair< int, int > P )
{
	if( St == Dr )
        ArbY[ Nod ].resize( 1, P.y );
	else
	{
		int M = St + ((Dr-St)>>1);

		if( Pos <= M ) UPDATE( (Nod<<1), St, M, Pos, P );
		else UPDATE( ((Nod<<1)|1), M + 1, Dr, Pos, P );

		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 <= Puncte[St].x && Puncte[Dr].x <= XB )
	{
		vector< int >::iterator Min = lower_bound( ArbY[ Nod ].begin(), ArbY[ Nod ].end(), YMIN );
		vector< int >::iterator Max = upper_bound( ArbY[ Nod ].begin(), ArbY[ Nod ].end(), YMAX );

		return (int)(Max - Min);
	}
	else if( St == Dr ) return 0;
	else if( St < Dr )
	{
		int M = St + ((Dr-St)>>1);
		int Rez = 0;

		if( XA <= Puncte[M].x ) Rez += QUERY( (Nod<<1), St, M, XA, XB, YMIN, YMAX );
		if( XB > Puncte[M].x ) 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 );
	sort( Puncte + 1, Puncte + N + 1 );

	for( i = 1; i <= N; ++i )
		UPDATE( 1, 1, N, i, Puncte[i] );

	scanf("%d", &Q);
	for( ; Q--; )
	{
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2 );
		printf("%d\n", QUERY( 1, 1, N, x1, x2, y1, y2 ) );
	}

	return 0;
}