Cod sursa(job #495387)

Utilizator cosmyoPaunel Cosmin cosmyo Data 24 octombrie 2010 22:22:56
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define x first
#define y second
#define inf 2000000005
using namespace std;
const int N=65005;
vector<int> v[N];
vector < pair<int,int> > p(N);
int p1,p2,x1,x2,y1,y2,m,x[N],y[N],n,ind[N];
void constr(int st,int dr,int poz)
{	
	if(st==dr)
	{ind[st]=poz;
	 return ;
	}
  int m=(st+dr)/2;
  constr(st,m,poz*2);
  constr(m+1,dr,poz*2+1);
}
void update(int poz,int val)
{int x=ind[poz];
 v[x].push_back(val);
 
  for(x/=2;x;x/=2)
   v[x].resize(v[2*x].size()+v[2*x+1].size()),merge(v[2*x].begin(),v[2*x].end(),v[2*x+1].begin(),v[2*x+1].end(),v[x].begin());
}
int query(int st,int dr,int poz)
{int x,y;
   if(p1>dr||p2<st)
	   return 0;
  if(p1<=st&&dr<=p2)
  {x=lower_bound(v[poz].begin(),v[poz].end(),y1)-v[poz].begin();
   y=upper_bound(v[poz].begin(),v[poz].end(),y2)-v[poz].begin();
   return y-x;
  }
  int mij=(st+dr)/2;
  return query(st,mij,poz*2)+query(mij+1,dr,poz*2+1);

}

int main()
{freopen("zoo.in","r",stdin);
 freopen("zoo.out","w",stdout);
  scanf("%d ",&n);
  	int i,j;
		for(i=1;i<=n;++i)
		{	scanf("%d%d",&p[i].x,&p[i].y);x[i]=p[i].x;}
 
	sort(x+1,x+n+1);
  
 	
		for(i=1;i<=n;++i)
			p[i].x=lower_bound(x+1,x+n+1,p[i].x)-x;
         
	 constr(1,n,1);		
   
	for(i=1;i<=n;++i)
		update(p[i].x,p[i].y);
	  
  
  scanf("%d",&m);
   for(i=1;i<=m;++i)
	{scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
	 p1=lower_bound(x+1,x+n+1,x1)-x;
	 p2=lower_bound(x+1,x+n+1,x2)-x;
	 printf("%d\n",query(1,n,1));
	}
 return 0;
}