Cod sursa(job #426051)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 26 martie 2010 13:14:31
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.99 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#define NMAX 16005
#define LMAX 1<<15
#define pb push_back
using namespace std;
int n,m,init[NMAX];
struct pct
{
	int a,b;
};
pct A[NMAX];
struct arb
{
	int a,b;
};
arb B[LMAX];
int x1,y1,x2,y2,rez;
vector <int> H[LMAX];
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%d%d",&A[i].a,&A[i].b);
	scanf("%d",&m);
}
bool comp(pct x,pct y)
{
	if (x.a<y.a)
		return 1;
	if (x.a>y.a)
		return 0;
	if (x.b<y.b)
		return 1;
	return 0;
}
void interclaseaza(int poz)
{
	int i=0,j=0,sz1=H[2*poz].size()-1,sz2=H[2*poz+1].size()-1;
	while (i<=sz1 && j<=sz2)
	{
		if (H[2*poz][i]<H[2*poz+1][j])
		{
			H[poz].pb(H[2*poz][i]);
			i++;
		}
		if (H[2*poz][i]>=H[2*poz+1][j])
		{
			H[poz].pb(H[2*poz+1][j]);
			j++;
		}
	}
	while (i<=sz1)
	{
		H[poz].pb(H[2*poz][i]);
		i++;
	}
	while (j<=sz2)
	{
		H[poz].pb(H[2*poz+1][j]);
		j++;
	}
}
void cstr(int st, int dr, int poz)
{
	if (st==dr)
	{
		init[st]=poz;
		B[poz].a=A[st].a; B[poz].b=A[st].a;
		H[poz].pb(A[st].b);
		return;
	}
	int mij=(st+dr)/2;
	cstr(st,mij,2*poz);
	cstr(mij+1,dr,2*poz+1);
	B[poz].a=B[2*poz].a; B[poz].b=B[2*poz+1].b;
	interclaseaza(poz);
}
int cbin(int poz,int val)
{
	int i,step,sz=H[poz].size();
	for (step=1; step<=sz; step<<=1);
	for (i=0; step; step>>=1)
		if (i+step<=sz && H[poz][i+step-1]<=val)
			i+=step;
	return i;
}
void answer(int poz)
{
	int poz1,poz2;
	poz1=cbin(poz,y2);
	poz2=cbin(poz,y1-1);
	rez+=poz1-poz2;
}
void caut(int st,int dr,int poz)
{
	if (x1<=B[poz].a && B[poz].b<=x2)
	{
		answer(poz);
		return ;
	}
	if (x2<B[poz].a || x1>B[poz].b)
		return ;
	int mij=(st+dr)/2;
	caut(st,mij,2*poz);
	caut(mij+1,dr,2*poz+1);
}
int main()
{
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	read();
	sort(A+1,A+n+1,comp);
	cstr(1,n,1);
	while (m--)
	{
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
		rez=0;
		caut(1,n,1);
		printf("%d\n",rez);
	}
	return 0;
}