Cod sursa(job #862396)

Utilizator aladinaladin aladinn aladin Data 22 ianuarie 2013 17:55:07
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define pi pair<int,int>
#define x first
#define y second
#define LG 21
#define Nmax 16005

int A[LG][Nmax],n,m;
pi v[Nmax];

int aplic(int lev,int l,int r,int a,int b)
{

	int st,dr,s1,s2,mij;
	st=l;dr=r;s1=r+1;
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if(a<=A[lev][mij])
		{
			dr=mij-1;
			s1=mij;
		}
		else
		st=mij+1;
	}
	if(s1==r+1) return 0;
	st=l;dr=r;s2=l-1;
	while(st<=dr)
	{
		mij=(st+dr)/2;
		if(b>=A[lev][mij])
		{
			st=mij+1;
			s2=mij;
		}
		else
			dr=mij-1;
	}
	return s2-s1+1;
}

void build(int lev,int l,int r)
{
	if (l==r)
	{
		A[lev][l]=v[l].y;
		return ;
	}
	int mij=(l+r)/2;
	build(lev+1,l,mij);
	build(lev+1,mij+1,r);
	int st,dr,poz;
	st=l; dr=mij+1; poz=l;
	while(poz<=r)
	{
		if(dr>r || (st<=mij && A[lev+1][st]<=A[lev+1][dr]))
		{
			A[lev][poz]=A[lev+1][st];
			poz++; st++;
		}
		else
		{
			A[lev][poz]=A[lev+1][dr];
			poz++; dr++;
		}
	}
}
int query(int lev,int l,int r,pi a,pi b)
{
	if(a.x<=l && r<=b.x)
	{
		int sol=aplic(lev,l,r,a.y,b.y);
		return sol;
	}
	int mij=(l+r)/2,s1=0,s2=0;
	
	if(a.x<=mij)
		s1=query(lev+1,l,mij,a,b);
	if (b.x>mij)
		s2=query(lev+1,mij+1,r,a,b);
	return s1+s2;
}
int main ()
{
	int i,st,dr,mij,sol=0;
	pi a,b;
	
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d%d",&v[i].x,&v[i].y);
	sort(v+1,v+n+1);
	build(1,1,n);
	scanf("%d",&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&a.x,&a.y,&b.x,&b.y);
		st=1;dr=n;sol=n+1;
		while(st<=dr)
		{
			mij=(st+dr)/2;
			if(v[mij].x>=a.x)
			{
				sol=mij;
				dr=mij-1;
			}
			else
				st=mij+1;
		}
		a.x=sol;sol=0;
		st=1;dr=n;
		
		while(st<=dr)
		{
			mij=(st+dr)/2;
			if(v[mij].x<=b.x)
			{
				sol=mij;
				st=mij+1;
			}
			else
				dr=mij-1;
		}
		b.x=sol;
		int sol=0;
		if (a.x<=b.x)
			sol=query(1,1,n,a,b);
		printf("%d\n",sol);
	}
	return 0;
}