Cod sursa(job #79550)

Utilizator blasterzMircea Dima blasterz Data 23 august 2007 01:02:45
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.93 kb
using namespace std;
#include <cstdio>
#include <vector>
#include <algorithm>
#define maxn 16001
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)|1)
#define md(i, j) (((i)+(j))>>1)
#define pb push_back
struct nod { int x, y; nod(){}; nod(int a, int b){x=a; y=b;};};
struct cmp{ 
	bool operator()(const nod &a, const nod &b)const
	{
		if(a.x<b.x) return 1;
		if(a.x==b.x && a.y<b.y) return 1;
		return 0;
	}
};
struct cmp2{ 
	bool operator()(const nod &a, const nod &b)const
	{
		if(a.y<b.y) return 1;
		if(a.y==b.y && a.x<b.x) return 1;
		return 0;
	}
};

nod a[maxn];
int X1, X2;
vector<nod> H[maxn*3];
int N, M;
int x1, y1, x2, y2;
void read()
{
	int i;
	freopen("zoo.in","r",stdin);
	scanf("%d\n", &N);
	for(i=1;i<=N;++i) 
		scanf("%d %d\n", &a[i].x, &a[i].y);
	sort(a+1, a+N+1, cmp());
}

void build(int n, int l, int r)
{
	if(l==r){H[n].pb(a[l]); return;}
	
	for(int i=l;i<=r;++i)H[n].pb(a[i]);
	sort(H[n].begin(), H[n].end(),cmp2());
	int m=md(l, r);
	/*
	if(l==1 && r==2) 
	{
		printf("da\n");
		for(int i=0;i<H[n].size();++i)printf("%d ", H[n][i]);
		printf("\n\n");
	}
	*/
	build(left(n), l, m);
	build(right(n), m+1, r);
}

inline int bsearch(vector<nod>a, int l, int r, int P)
{
	//printf("%d\n", P);
	int i, cnt, pi=-1, pj=-1, n=a.size();
	//if(y2<a[0].y) return 0;
	//if(y1>a[n-1].y)return 0;
	for(i=0, cnt=(1<<20);cnt;cnt>>=1)
		if(i+cnt<n)
			if(a[i+cnt].y<=y2)i+=cnt;
	pj=i;
	
	for(i=n-1, cnt=(1<<20);cnt;cnt>>=1)
		if(i-cnt>=0)
			if(a[i-cnt].y>=y1)i-=cnt;
	pi=i;
		//printf("da %d %d\n", l, r);
	//for(i=0;i<n;++i)printf("%d ", a[i].y);
	//printf("\n\n");
	//		printf("(%d %d)\n", pi, pj);
	return pj-pi+1;
}

int query(int n, int l, int r)// x1, x2, y1, y2
{
	if(x1<=l && r<=x2)
	{
	//	if (y2 < H[n][0].y || y1 > H[n][H[n].size()-1].y) 
     //     return 0;
      // if (y1 < H[n][0].y && H[n][H[n].size()-1].y < y2) 
        //  return (r - l + 1);

		return bsearch(H[n], l, r,n); 
		int nr=0;
		for(int i=l;i<=r;++i)
			if(a[i].y>=y1 && a[i].y<=y2)++nr;
		return nr;
	}
	int m=md(l, r);
	int s=0;
	
	if(x1<=m) s+=query(left(n), l, m);
	if(x2>m) s+=query(right(n), m+1, r);
	return s;
}



int main()
{
	freopen("zoo.out","w",stdout);
	read();
	build(1, 1, N);
	//for(int i=1;i<=N;++i)printf("%d %d\n", a[i].x, a[i].y);
	//printf("\n");
	int m;
	scanf("%d\n", &m);
	int  i, cnt;
	while(m--)
	{
		scanf("%d %d %d %d\n", &x1, &y1, &x2, &y2);
		X1=x1;X2=x2;
		//	printf("__%d %d__\n", x1, x2);
		for(i=1, cnt=(1<<20);cnt;cnt>>=1)
			if(i+cnt<=N)
				if(a[i+cnt].x<=x2) i+=cnt;
		//while(i<=N && a[i].x==x2) ++i;
		//if(a[i].x>x2)--i;
		x2=i;
		
		for(i=N, cnt=(1<<20);cnt;cnt>>=1)
			if(i-cnt>=1)
				if(a[i-cnt].x>=x1) i-=cnt;
		//while(i>0 && a[i].x==x1) --i;
		///if(a[i].x<x1) ++i;
		x1=i;
		printf("%d\n", query(1, 1, N));
		//for(i=x1;i<=x2;++i)printf("%d %d\n", a[i].x, a[i].y);
		//printf("%d %d\n\n", x1, x2);
		
	}
return 0;
}