Cod sursa(job #603574)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 17 iulie 2011 15:32:04
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include<stdio.h>
#include<algorithm>
#include<vector>

#define maxN 16005

using namespace std;

FILE*f=fopen("zoo.in","r");
FILE*g=fopen("zoo.out","w");

struct pct{
	int x;
	int y;
}V[maxN];

struct arb{
	vector<int>G;
}A[4*maxN];

int n,i,a,b,p,m,u,l1,l2,q,nr,x1,y1,x2,y2;

struct cmp1{
	inline bool operator () ( const pct &a, const pct &b ){
		if ( a.x != b.x )
			return a.x < b.x;
		return a.y <= b.y;
	}
};

inline void citire () {
	
	fscanf(f,"%d",&n);
	
	for ( i = 1 ; i <= n ; ++i ){
		fscanf(f,"%d %d",&V[i].x,&V[i].y);
	}
}

inline bool smaller ( pct a , pct b ){
	if ( a.y != b.y ){
		return a.y < b.y;
	}
	return a.x < b.x;
}

void update ( int nod , int st , int dr ){
	
	if ( st == dr ){
		A[nod].G.push_back(st);
		return ;
	}
	
	int mij = (st + dr) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	update( nodst , st, mij );
	update( noddr, mij + 1, dr );
	
	int i,j;
	for ( i = j = 0 ; i < A[nodst].G.size() && j < A[noddr].G.size() ; ){
		if ( smaller(V[A[nodst].G[i]],V[A[noddr].G[j]]) ){
			A[nod].G.push_back( A[nodst].G[i++] );
		}
		else{
			A[nod].G.push_back( A[noddr].G[j++] );
		}
	}
	
	for ( ; i < A[nodst].G.size() ; )
		A[nod].G.push_back( A[nodst].G[i++] );
	for ( ; j < A[noddr].G.size() ; )
		A[nod].G.push_back( A[noddr].G[j++] );
}

inline void cb1 () {
	
	p = 1; u = n ;
	
	while ( p <= u ){
		m = (p + u) >> 1;
		if ( V[m].x >= x1 )
			u = m - 1;
		else
			p = m + 1;
	}
	
	a = p;
}

inline void cb2 () {
	
	p = 1; u = n;
	
	while ( p <= u ){
		m = (p + u) >> 1;
		if ( V[m].x <= x2 )
			p = m + 1;
		else
			u = m - 1;
	}
	
	b = u;
}

void query ( int nod , int st , int dr ){
	
	if ( a <= st && dr <= b ){
		
		p = 0 ; u = A[nod].G.size() - 1;
		
		while ( p <= u ){
			m = (p + u) >> 1;
			if ( V[ A[nod].G[m] ].y >= y1 )
				u = m - 1;
			else
				p = m + 1;
		}
		l1 = p;
		
		p = 0; u = A[nod].G.size() - 1;
		
		while ( p <= u ){
			m = (p + u) >> 1;
			if ( V[ A[nod].G[m] ].y <= y2 )
				p = m + 1;
			else
				u = m - 1;
		}
		l2 = u;
		
		nr += l2 - l1 + 1;
		
		return ;
	}
	
	int mij = (st + dr) >> 1;
	int nodst = nod << 1;
	int noddr = nodst + 1;
	
	if ( a <= mij ){
		query(nodst,st,mij);
	}
	if ( b > mij ){
		query(noddr,mij+1,dr);
	}
}

inline void solve () {
	
	sort( V+1,V+n+1,cmp1() );
	
	update(1,1,n);
	
	fscanf(f,"%d",&q);
	
	for ( ; q ; --q ){
		fscanf(f,"%d %d %d %d",&x1,&y1,&x2,&y2);
		cb1(); cb2();
		nr = 0;
		if ( a <= b ){
			query(1,1,n);
		}
		fprintf(g,"%d\n",nr);
	}
}

int main () {
	
	citire();
	solve();
	
	fclose(f);
	fclose(g);
	
	return 0;
}