Cod sursa(job #784192)

Utilizator ELHoriaHoria Cretescu ELHoria Data 5 septembrie 2012 01:33:34
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define x first
#define y second

using namespace std;

const int NMAX = 16005;
pair<int,int> p[NMAX];
vector<int> aint[NMAX<<2];
int N , Q ;

void build(const int &nod,const int &st,const int &dr)
{
	if(st == dr) {
		aint[nod].push_back(p[st].y); 
		return; 
	}
	int mid = (st + dr)>>1 , leftSon = nod<<1 , rightSon = (nod<<1) + 1;
	build(leftSon,st,mid);
	build(rightSon,mid + 1,dr);
	int dimLeft =(int)aint[leftSon].size()  , dimRight = (int)aint[rightSon].size();
	aint[nod].resize(dimLeft + dimRight);
	//merge
	for(int i = 0 , j = 0  , k = 0;i < dimLeft || j < dimRight;k++) {
		if(i == dimLeft) {
			aint[nod][k] = aint[rightSon][j++];
		}
		else 
		if(j == dimRight) {
			aint[nod][k] = aint[leftSon][i++];
		} else {
			aint[nod][k] = aint[leftSon][i] < aint[rightSon][j] ? aint[leftSon][i++] : aint[rightSon][j++];
		}
	}
}

int query(const int &nod,const int &st,const int &dr,const int &xa,const int &xb,const int &ya,const int &yb)
{
	if(xa <= p[st].x && p[dr].x <= xb)
		return (lower_bound(aint[nod].begin(),aint[nod].end(),yb + 1) - lower_bound(aint[nod].begin(),aint[nod].end(),ya));
	if(st == dr) return 0;
	int mid = (st + dr)>>1 , leftSon = nod<<1 , rightSon = (nod<<1) + 1;
	if(p[mid + 1].x > xb) return query(leftSon,st,mid,xa,xb,ya,yb);
	if(p[mid].x < xa) return query(rightSon,mid + 1,dr,xa,xb,ya,yb);
	return query(leftSon,st,mid,xa,p[mid].x,ya,yb) + query(rightSon,mid + 1,dr,p[mid + 1].x,xb,ya,yb);
}

int main()
{
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	scanf("%d",&N);
	for(int i = 0;i < N;++i) {
		scanf("%d %d",&p[i].x,&p[i].y);
	}
	sort(p,p + N);

	build(1,0,N - 1);
	
	int xa , xb , ya , yb;
	for(scanf("%d",&Q);Q;Q--) {
		scanf("%d %d %d %d",&xa,&ya,&xb,&yb);
		printf("%d\n",query(1,0,N - 1,max(xa,p[0].x),min(xb,p[N - 1].x),ya,yb));
	}
	
	return 0;
}