Cod sursa(job #79900)

Utilizator gigi_becaliGigi Becali gigi_becali Data 24 august 2007 15:11:39
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
using namespace std;
#include <map>
#include <hash_map.h>
#include <cstdio>
#define maxn 16001
#define maxv 1000000000
#include <set>
#include <list>
#define maxh 666013
#define ui unsigned int
#define prime 17
inline int bit(int x){ return (x&((x-1)^x));}
struct nod { int x, y; unsigned int x1, y1;};

hash_map<ui, map<ui, ui> , hash<ui> > BIT;
nod a[maxn];
int n;

struct nd { ui x, y; ui v;nd(){}; nd(ui a, ui b){x=a; y=b; v=1;};};

list<nd>H[maxh];
inline ui hashf(ui i, ui j)
{
	i=i%maxh;
	j=j%maxh;
	return (i*prime+maxh+j)%maxh;
}


void read()
{
	freopen("zoo.in","r",stdin);
	scanf("%d\n", &n);
	int i;
	for(i=1;i<=n;++i) scanf("%d %d\n", &a[i].x, &a[i].y);
}

void update(ui x, ui y)
{
	ui i, j, p, found;
	list<nd>::iterator it;
	for(i=x;i<=(maxv<<1)+1; i+=bit(i))
		for(j=y;j<=(maxv<<1)+1 ;j+=bit(j))
		{
			p=hashf(i, j);
			found=0;
			for(it=H[p].begin();it!=H[p].end();++it)
				if(it->x==i && it->y==j) {found=1;break;}
			if(found)it->v++;
				else H[p].push_back(nd(i, j));
			//	printf("%d %d\n", i, j);
			//++BIT[i][j];
		}
}

ui query(ui x, ui y)
{
	ui s=0, i, j, p;
	list<nd>::iterator it;
	for(i=x;i>0;i-=bit(i))
		for(j=y;j>0;j-=bit(j))
		{
			p=hashf(i, j);
			for(it=H[p].begin();it!=H[p].end();++it)
				if(it->x==i && it->y==j) { s+=it->v; break;}
	//		s+=BIT[i][j];
		}
	return s;
}

int main()
{
	freopen("zoo.out","w",stdout);
	read();
	int i, m,x1, x2, y1, y2;
	for(i=1;i<=n;++i) a[i].x1=(ui)a[i].x+maxv, a[i].y1=(ui)a[i].y+maxv;
	for(i=1;i<=n;++i)update(a[i].x1, a[i].y1);
	
	scanf("%d\n", &m);
	unsigned int X1, Y1, X2, Y2;
	while(m--)
	{
		scanf("%d %d %d %d\n", &x1, &y1, &x2, &y2);
		X1=(ui)x1+maxv, Y1=(ui)y1+maxv, X2=(ui)x2+maxv, Y2=(ui)y2+maxv;
		//printf("__%d %d %d %d\n", x1, x2, y1, y2);
		//printf("(%d %d %d %d\n", query(x2, y2), query(x1-1 ,y1-1), query(x2, y1-1), query(x1-1, y2));
		ui s=query(X2, Y2)+query(X1-1, Y1-1)-query(X2, Y1-1)-query(X1-1, Y2);
		printf("%d\n", s);
		
	}
	return 0;
}