Cod sursa(job #107463)

Utilizator gigi_becaliGigi Becali gigi_becali Data 19 noiembrie 2007 21:15:56
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.77 kb
using namespace std;
#include <cstdio>
#include <vector>
#include <cstdlib>
#include <ctime>
#define maxn 600011
#define bit(x)   (((x) & ((x)-1)) ^ (x))
#define pb push_back
#define ui unsigned int 
#define maxv 1000000000
struct nod { unsigned int x, y, nr; nod(){}; nod(unsigned int a, unsigned int b,unsigned  int c){x=a; y=b;nr=c;};};

vector<nod>H[maxn];
unsigned int N=maxv;


inline void insert(unsigned int i,unsigned  int j)
{
  unsigned int h=(((i%maxn)*17)%maxn+(((j)%maxn)*11)%maxn)%maxn;
  vector<nod>::iterator it;
  for(it=H[h].begin();it!=H[h].end();++it)
    if(it->x==i && it->y==j)
      {
	++it->nr;
	return ;
      }
  H[h].pb(nod(i, j, 1));
}

inline unsigned int find(unsigned int i, unsigned int j)
{
  unsigned int h=(((i%maxn)*17)%maxn+(((j)%maxn)*11)%maxn)%maxn;
  vector<nod>::iterator it;
  for(it=H[h].begin();it!=H[h].end();++it)
    if(it->x==i && it->y==j) return it->nr;
  return 0;
}

inline void update(unsigned int x, unsigned int y)
{
  for(unsigned int i=x; i<=(maxv<<1)+1; i+=bit(i))
    for(unsigned int j=y; j<=(maxv<<1)+1; j+=bit(j)) insert(i, j);
}

inline unsigned int query(unsigned int x, unsigned int y)
{
  unsigned int s=0;
  for(unsigned int i=x; i>0; i-=bit(i))
    for(unsigned int j=y; j>0; j-=bit(j)) s+=find(i, j);
  return s;
}

char ax[100000*45];
int n;
void read()
{
	freopen("zoo.in","r",stdin);
	scanf("%d\n", &n);
	int i;
	int x, y;
	unsigned int x1, y1;
	for(i=1;i<=n;++i)
	  {
	    scanf("%d %d\n", &x, &y);
	    x1=(unsigned int) x+maxv;
	    y1=(unsigned int) y+maxv;
	    update(x1, y1);
	  }
}

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);
	fread(ax, sizeof(char), m*44, stdin);
	char *p;
	
	unsigned int X1, Y1, X2, Y2;
	
	m--;
	p=strtok(ax, " ");
	x1=atoi(p);
	p=strtok(0, " ");
	y1=atoi(p);
	p=strtok(0, " ");
	x2=atoi(p);
	p=strtok(0, " \n");
	y2=atoi(p);
	
	

	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);

	
	while(m--)
	{
		p=strtok(0, " ");
		x1=atoi(p);
		p=strtok(0, " ");
		y1=atoi(p);
		p=strtok(0, " ");
		x2=atoi(p);
		p=strtok(0, " \n");
		y2=atoi(p);
		
	//	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;
}