Cod sursa(job #79894)

Utilizator gigi_becaliGigi Becali gigi_becali Data 24 august 2007 14:57:54
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
using namespace std;
#include <map>
#include <cstdio>
#define maxn 16001
#define maxv 1000000000
#define ui unsigned int

inline int bit(int x){ return (x&((x-1)^x));}
struct nod { int x, y; unsigned int x1, y1;};

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


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;
	for(i=x;i<=(maxv<<1)+1; i+=bit(i))
		for(j=y;j<=(maxv<<1)+1 ;j+=bit(j))
		{
		//	printf("%d %d\n", i, j);
			++BIT[i][j];
		}
}

ui query(ui x, ui y)
{
	ui s=0, i, j;
	for(i=x;i>0;i-=bit(i))
		for(j=y;j>0;j-=bit(j))
			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;
}