Cod sursa(job #79575)

Utilizator gigi_becaliGigi Becali gigi_becali Data 23 august 2007 09:15:19
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.88 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
#define ui int
struct nod { ui x, y; nod(){}; nod(ui a, ui 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];
ui X1, X2;
vector<int> H[maxn*3];
ui N, M;
ui x1, y1, x2, y2;
void read()
{
	ui 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 rad(vector<int>&a, vector<int>&b,int byte)
{
	int count[256], index[256];
	memset(count, 0,sizeof(count));
	int i, n=a.size();
	for(i=0;i<n;++i) ++count[(a[i]>>byte)&255];
	index[0]=0;
	for(i=1;i<256;++i) index[i]=index[i-1]+count[i-1];
	for(i=0;i<n;++i) b[index[(a[i]>>byte)&255]++]=a[i];
}

vector<int> radix(vector<int>&a)
{
	vector<int>b(a.begin(), a.end());
	rad(a, b, 0);
	rad(b, a, 8);
	rad(a, b, 16);
	rad(b, a, 24);
return a;
}


void build(ui n, ui l, ui r)
{
	if(l==r){H[n].pb(a[l].y); return;}
	ui m=md(l, r);		
//	for(ui i=l;i<=r;++i)H[n].pb(a[i].y);
	//sort(H[n].begin(), H[n].end());//,cmp2());
	//H[n]=radix(H[n]);
	build(left(n), l, m);
	build(right(n), m+1, r);


	int i,j, N=H[left(n)].size(), M=H[right(n)].size();
	H[n].reserve(N+M+1);
	for(i=0, j=0;i<N && j<M;)
		if(H[left(n)][i]>H[right(n)][j])H[n].pb(H[right(n)][j]), ++j;
		else H[n].pb(H[left(n)][i]),++i;
		//printf("%d %d %d %d\n", i, j, N, M);
		if(j<M)
		{
			//printf("da\n");
			for(;j<M;++j) H[n].pb(H[right(n)][j]);
		}
		if(i<N)
		{
			///printf("da\n");
			for(;i<N;++i) H[n].pb(H[left(n)][i]);
		}
		//for(i=0;i<H[n].size();++i)printf("%d ", H[n][i]);
	//		printf("\n\n");
	
	/*
	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");
	}
	*/

}

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

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

		return bsearch(H[n], l, r,n); 
		ui nr=0;
		for(ui i=l;i<=r;++i)
			if(a[i].y>=y1 && a[i].y<=y2)++nr;
		return nr;
	}
	ui m=md(l, r);
	ui 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");
	ui m;
	scanf("%d\n", &m);
	ui  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<<15);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<<15);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;
}