Cod sursa(job #365667)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 19 noiembrie 2009 16:26:47
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.68 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=0;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);
		Ai[2*nod+1].push_back(Inf);
		
		int i,nr1=0,nr2=0;
		
		for (i=0;i<=ld-ls;++i)
			 if (Ai[2*nod][nr1]>=Ai[2*nod+1][nr2])
			 {
				 Ai[nod].push_back(Ai[2*nod+1][nr2]);
				 nr2++;
			 }
			 else
			 {
				 Ai[nod].push_back(Ai[2*nod][nr1]);
				 nr1++;
			 } 	 
	}
}

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

int search2(int nod,int ls,int ld,int x)
{
         int mij,rez=-1;
         
         while (ls<=ld)
           {
               mij=(ld+ls)>>1;
               if (x>=Ai[nod][mij])
                 {
                    rez=mij;
                    ls=mij+1;
                 }
               else ld=mij-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,0,ld-ls,y1);
		yy=search2(nod,0,ld-ls,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,p+N);
	
	update(1,0,N-1);
	
	while(M--)
	{
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		rez=0;
		query(1,0,N-1);
		printf("%d\n", rez);
	}
}


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

	scanf("%d", &N);
	for (i=0;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;
	
}