Cod sursa(job #432804)

Utilizator swift90Ionut Bogdanescu swift90 Data 2 aprilie 2010 19:38:15
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.88 kb
#include<stdio.h>
#include<utility>
#include<algorithm>
using namespace std;
#define lg 16100
#define fs first
#define sc second
int N,M,init[lg],X[lg],x1,y1,x2,y2,sol;
int *arb[4*lg];
char fol[4*lg];
pair<int,int> nr[lg];
void constr(int st,int dr,int poz){
	if(st==dr){
		init[st]=poz;
		return;
	}
	int mij=(st+dr)/2;
	constr(st,mij,poz*2);
	constr(mij+1,dr,poz*2+1);
}
void update(int a,int b,int poz){
	int x=init[poz],i,j;
	arb[x]=new int [b-a+5];
	arb[x][0]=0;
	for(i=a;i<=b;++i)
		arb[x][++arb[x][0]]=nr[i].sc;
	fol[x]=1;
	x>>=1;
	while(x && fol[x*2] && fol[1+x*2]){
		a=arb[x<<1][0],b=arb[1+(x<<1)][0];
		arb[x]=new int [a+b+5];
		for(i=1,j=1,arb[x][0]=0;i<=a && j<=b;){
			if(arb[x<<1][i]<arb[1+(x<<1)][j])
				arb[x][++arb[x][0]]=arb[x<<1][i++];
			else
				arb[x][++arb[x][0]]=arb[1+(x<<1)][j++];
		}
		for(;i<=a;++i)
			arb[x][++arb[x][0]]=arb[x<<1][i];
		for(;j<=b;++j)
			arb[x][++arb[x][0]]=arb[1+(x<<1)][j];
		fol[x]=1;
		x>>=1;
	}
}
void query(int st,int dr,int poz){
	if(X[st]>x2 || x1>X[dr])
		return;
	if(x1<=X[st] && X[dr]<=x2){
		sol+=(upper_bound(arb[poz]+1,arb[poz]+arb[poz][0]+1,y2)-lower_bound(arb[poz]+1,arb[poz]+arb[poz][0]+1,y1));
		return;
	}
	if(st<dr){
		int mij=(st+dr)/2;
		query(st,mij,poz*2);
		query(mij+1,dr,1+poz*2);
	}
}
int main(){
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	int i,j,k;
	scanf("%d",&N);
	for(i=1;i<=N;++i)
		scanf("%d%d",&nr[i].fs,&nr[i].sc);
	sort(nr+1,nr+N+1);
	nr[0].fs=(1<<31)-1;
	for(i=1;i<=N;++i){
		if(nr[i].fs!=nr[i-1].fs)
			X[++X[0]]=nr[i].fs;
	}
	constr(1,X[0],1);
	for(i=1,k=1;i<=N;++i,++k){
		j=i;
		while(nr[j].fs==nr[i].fs && j<=N)
			++j;
		update(i,j-1,k);
		i=j-1;
	}
	scanf("%d",&M);
	for(i=0;i<M;++i){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		sol=0;
		query(1,X[0],1);
		printf("%d\n",sol);
	}
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}