Cod sursa(job #496364)

Utilizator cosmyoPaunel Cosmin cosmyo Data 28 octombrie 2010 17:53:41
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define x first
#define y second
#define inf 2000000005
using namespace std;
const int N=65000;
const int NM=16005;
vector<int> v[N];
vector < pair<int,int> > p(NM);
int p1,p2,x1,x2,y1,y2,m,x[NM],y[NM],n,ind[NM];
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].push_back(val);
}
int query(int st,int dr,int poz)
{int x,y;
   if(p1>dr||p2<st)
	   return 0;
  if(p1<=st&&dr<=p2)
  {x=upper_bound(v[poz].begin(),v[poz].end(),y1-1)-v[poz].begin();
   y=upper_bound(v[poz].begin(),v[poz].end(),y2)-v[poz].begin();
   return y-x;
  }
  int mij=(st+dr)/2,s1=0,s2=0;
   if(p1<=mij)
    s1=query(st,mij,poz*2);
   if(mij<p2)
    s2=query(mij+1,dr,poz*2+1);
 return s1+s2;
}
int cmp(pair<int,int> a,pair<int,int> b)
{return a.y<b.y;
}
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);
    sort(p.begin()+1,p.begin()+n+1,cmp);
	for(i=1;i<=n;++i)
		update(p[i].x,p[i].y);

  int k[5]={1,2,2,2,10};
  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=upper_bound(x+1,x+n+1,x2)-x-1;
	 printf("%d\n",query(1,n,1));
	}
 return 0;
}