Cod sursa(job #365664)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 19 noiembrie 2009 16:14:03
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define file_in "zoo.in"
#define file_out "zoo.out"

#define Nmax 16010

#define f first
#define s second

#define Inf 2001000100

int N,M;
pair<int, int> p[Nmax];
int x1,y1,x2,y2,rez;
vector<int> Ai[4*Nmax];

void brute()
{
	int nr,i;
	
	while(M--)
	{
		nr=0;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		
		for (i=1;i<=N;++i)
			 if (x1<=p[i].f && p[i].f<=x2 && y1<=p[i].s && p[i].s<=y2)
				 nr++;
			 
		printf("%d\n", nr);
	}
}	

void update(int nod, int ls, int ld)
{
	if (ls==ld)
	{
		Ai[nod].push_back(p[ls].s);
	}
	else
	{
		int mij=(ls+ld)>>1;
		
		update(2*nod,ls,mij);
		update(2*nod+1,mij+1,ld);
		
		Ai[2*nod].push_back(Inf+1);
		Ai[2*nod+1].push_back(Inf+1);
		
		int i,nr1=0,nr2=0;
		
		for (i=1;i<=ld-ls+1;++i)
			 if (Ai[2*nod][nr1]>Ai[2*nod+1][nr2])
			 {
				 Ai[nod].push_back(Ai[2*nod][nr1]);
				 nr1++;
			 }
			 else
			 {
				 Ai[nod].push_back(Ai[2*nod+1][nr2]);
				 nr2++;
			 } 	 
	}
}

inline int search1(int nod,int ls, int ld, int x)
{
	int mij,rez=-1;
	
	while(ls<=ld)
	{
		mij=(ls+ld)>>1;
		
		if (x<=Ai[nod][mij])
		{
			rez=mij;
			mij=ld-1;
		}
		else
			mij=ls+1;
	}
	
	return rez;
}

inline int search2(int nod,int ls, int ld, int x)
{
	int mij,rez=-1;
	
	while(ls<=ld)
	{
		mij=(ls+ld)>>1;
		
		if (x>=Ai[nod][mij])
		{
			rez=mij;
			mij=ls+1;
		}
		else
			mij=ld-1;
	}
	
	return rez;
}
	

void query(int nod, int ls, int ld)
{
	int xx,yy;
	if (p[ls].f>=x1 && x2>=p[ld].f)
	{
		xx=search1(nod,1,ld-ls+1,y1);
		yy=search2(nod,1,ld-ls+1,y2);
		
		if (xx!=-1 && yy!=-1)
			rez+=yy-xx+1;
	}
	else
	if (ls!=ld)
	{
		
		int mij=(ls+ld)>>1;
		
		if (x1<=p[mij].f)
			query(2*nod,ls,mij);
		if (x2>=p[mij].f)
			query(2*nod+1,mij+1,ld);
	}
}

			
		
			


void solve()
{
	sort(p+1,p+N+1);
	
	update(1,1,N);
	
	while(M--)
	{
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		rez=0;
		query(1,1,N);
		printf("%d\n", rez);
	}
}


void citire()
{
	int i;
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);

	scanf("%d", &N);
	for (i=1;i<=N;++i)
		 scanf("%d %d", &p[i].f, &p[i].s);
	
	scanf("%d", &M);
	if (M<=1000)
	{
		brute();
	}
	else
	{
		solve();
	}
}
	
int main()
{
	citire();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}