Cod sursa(job #784187)

Utilizator ELHoriaHoria Cretescu ELHoria Data 5 septembrie 2012 01:05:40
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 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 , x[2] , y[2];

void build(int nod,int st,int dr)
{
	if(st == dr) {
		aint[nod].resize(1,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].y <= 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);
	for(scanf("%d",&Q);Q;Q--) {
		scanf("%d %d %d %d",&x[0],&y[0],&x[1],&y[1]);
		printf("%d\n",query(1,0,N - 1,max(x[0],p[0].x),y[0],min(x[1],p[N-1].y),y[1]));
	}
	return 0;
}