Cod sursa(job #828608)

Utilizator veleanduAlex Velea veleandu Data 3 decembrie 2012 23:27:58
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

	#define max_n 20000
	#define max_m 120000
	#define INF 2000000005
	#define pb push_back


	vector<int> El;

	struct point {
		int x,y,nr; 
	} Po[max_n],Ta[4*max_m];

	bool mysort ( point a, point b ){
		return a.y < b.y;
	}

    int Rez[4*max_m];
	int n,m,i,j,rez;

	int a,b,c,d,task;
	int Aib[6*max_m];


	void add ( int ind, int val ){
		for ( ; ind < 6*max_m; ind+=(ind)&(-ind) )
			Aib[ind]+=val;
	}
	int query ( int ind ){
		int rez=0;
		for ( ; ind; ind-=(ind)&(-ind) )
			rez+=Aib[ind];
		return rez;
	}

	int bs ( int val ){
		int ind=(1<<19),rez=0;
		for ( ; ind; ind>>=1 ){
			if ( rez+ind < int(El.size()) ){
				if ( El[ ind+rez ] <= val ){
					rez+=ind;
				}
			}
		}
		return rez;
	}

int main(){
	freopen ("zoo.in","r",stdin);
	freopen ("zoo.out","w",stdout);
	scanf ("%d", &n );
	for ( i=1; i<=n; i++ ){
		scanf ("%d %d", &Po[i].x, &Po[i].y );
		El.pb( Po[i].x );
		El.pb( Po[i].y );
	}
	El.pb( INF );
	El.pb( -INF );
	Po[n+1].x=INF;
	Po[n+1].y=INF;

	scanf ("%d", &m );
	for ( i=1; i<=m; i++ ){
		scanf ("%d %d %d %d", &a, &b, &c, &d );

		a--;
		b--;

		El.pb ( a );
		El.pb ( b );
		El.pb ( c );
		El.pb ( d );

		++task;
		Ta[task].x = a;
		Ta[task].y = b;
		Ta[task].nr = task;

		++task;
		Ta[task].x = c;
		Ta[task].y = d;
		Ta[task].nr = task;

		++task;
		Ta[task].x = a;
		Ta[task].y = d;
		Ta[task].nr = task;

		++task;
		Ta[task].x = c;
		Ta[task].y = b;
		Ta[task].nr = task;
	}
	Ta[ task+1 ].x = INF;
	Ta[ task+1 ].y = INF;

	sort ( El.begin(), El.end() );
 
 	sort ( Ta+1, Ta+4*m+1, mysort );
	sort ( Po+1, Po+n+1, mysort );

	int ind1=1, ind2=1, act;

	for ( ; ind1<=n || ind2<=4*m; ){
		act = min ( Po[ind1].y , Ta[ind2].y );
		// inseram punctele noi in AIB
		while ( (ind1<=n) && ( Po[ind1].y == act ) ){
			add ( bs ( Po[ind1].x ) , 1 );
			ind1++;
		}
		// facem queryurile 
		while ( ( ind2<=4*m ) && ( Ta[ind2].y == act ) ){
			Rez [ Ta[ind2].nr ] = query ( bs ( Ta[ind2].x ) );
			ind2++;
		}
	}

	for ( i=1; i<=m; i++ ){
		rez=0;
		rez += Rez[ (i-1)*4+1 ];
		rez += Rez[ (i-1)*4+2 ];
		rez -= Rez[ (i-1)*4+3 ];
		rez -= Rez[ (i-1)*4+4 ];
        printf("%d\n",rez);
	}

	return 0;
}