Cod sursa(job #79581)

Utilizator blasterzMircea Dima blasterz Data 23 august 2007 09:45:50
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.09 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;
int *H[maxn*3];
int len[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 build(ui n, ui l, ui r)
{
	if(l==r){H[n]=(int*)malloc(sizeof(int)*3); H[n][len[n]++]=a[l].y; return;}
	ui m=md(l, r);		
	build(left(n), l, m);
	build(right(n), m+1, r);


	int i,j, N=len[left(n)], M=len[right(n)];
	
	H[n]=(int*)malloc(sizeof(int)*(N+M+3));
	for(i=0, j=0;i<N && j<M;)
		if(H[left(n)][i]>H[right(n)][j])H[n][len[n]++]=H[right(n)][j], ++j;
		else H[n][len[n]++]=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][len[n]++]=H[right(n)][j];
		}
		if(i<N)
		{
			///printf("da\n");
			for(;i<N;++i) H[n][len[n]++]=H[left(n)][i];
		}
		//for(i=0;i<len[n];++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(int a[],int n, ui l, ui r)
{
	//printf("%d\n", P);
	ui i, cnt, pi=0, pj=0;
	
	for(i=0, cnt=(1<<20);cnt;cnt>>=1)
		if(i+cnt<n)
			if(a[i+cnt]<=y2)i+=cnt;
	pj=i;
	
	for(i=n-1, cnt=(1<<20);cnt;cnt>>=1)
		if(i-cnt>=0)
			if(a[i-cnt]>=y1)i-=cnt;
	pi=i;
	
	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][len[n]-1]) return 0;
        if (y1 < H[n][0] && H[n][len[n]-1] < y2)return (r - l + 1);
		return bsearch(H[n],len[n], l, r); 
	}
	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<<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;
}