Cod sursa(job #784191)

Utilizator ELHoriaHoria Cretescu ELHoria Data 5 septembrie 2012 01:23:27
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 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(int nod,int st,int dr)
{
	if(st == dr) {
		aint[nod].push_back(p[st].y); 
		return; 
	}
	int mid = (st + dr)>>1 , fiu = nod<<1 , fiu_ = (nod<<1) + 1;
	build(fiu,st,mid);
	build(fiu_,mid + 1,dr);
	aint[nod].resize(aint[fiu].size() + aint[fiu_].size());
	merge(aint[fiu].begin(),aint[fiu].end(),aint[fiu_].begin(),aint[fiu_].end(),aint[nod].begin());
}

int query(int nod,int st,int dr,int xa,int xb,int ya,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 , fiu = nod<<1 , fiu_ = (nod<<1) + 1;
	if(p[mid + 1].x > xb) return query(fiu,st,mid,xa,xb,ya,yb);
	if(p[mid].x < xa) return query(fiu_,mid + 1,dr,xa,xb,ya,yb);
	return query(fiu,st,mid,xa,p[mid].x,ya,yb) + query(fiu_,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;
}