Cod sursa(job #79809)

Utilizator gigi_becaliGigi Becali gigi_becali Data 23 august 2007 22:49:01
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 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*5];
int len[maxn*5];
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);
	for(;j<M;++j) H[n][len[n]++]=H[right(n)][j];
	for(;i<N;++i) H[n][len[n]++]=H[left(n)][i];
	/*
	printf("da\n");
	for(i=0;i<N;++i)printf("%d ", H[left(n)][i]);
	printf("\n");
	for(j=0;j<M;++j)printf("%d ", H[right(n)][j]);
	printf("\n");
	for(i=0;i<len[n];++i)printf("%d ", H[n][i]);
	printf("\n");
	*/

}

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

		for(i=1, cnt=(1<<15);cnt;cnt>>=1)
			if(i+cnt<=N)
				if(a[i+cnt].x<=x2) i+=cnt;

		x2=i;
		
		for(i=N, cnt=(1<<15);cnt;cnt>>=1)
			if(i-cnt>=1)
				if(a[i-cnt].x>=x1) i-=cnt;

		x1=i;
		printf("%d\n", query(1, 1, N));
		
	}
return 0;
}