Cod sursa(job #397212)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 16 februarie 2010 17:35:39
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include<iostream.h>
#include<fstream.h>

ifstream f("arbori2d.in");
ofstream g("arbori2d.out");


int x[20000],y[20000],arb[20][16010],n,x1,x2,yy,y2,p,s1,s2,q,m,a[20000],b[20000],l;


int cautbin(int st, int dr, int niv)
{
	p=1;
	s2=s1=st-1;
	for (;p<=(dr-st+1);p<<=1);
	p>>=1;
	q=p;
	for (;q>0;q>>=1)
		if (s1+q<=dr && arb[niv][s1+q]<yy)
			s1+=q;
	q=p;
	for (;q>0;q>>=1)
		if (s2+q<=dr && arb[niv][s2+q]<=y2)
			s2+=q;
	return s2-s1;
}
int querry (int k, int st, int dr, int niv)
{
	if (x[dr]<x1 || x[st]>x2) 
		return 0;
	if (x1<=x[st] && x2>=x[dr])
		return cautbin(st,dr,niv);
	int mij=(st+dr)/2;
	return querry(2*k,st,mij,niv+1)+querry(2*k+1,mij+1,dr,niv+1);
}

void compute()
{
	int i,j;
	f>>m;
	for (i=1;i<=m;i++)
	{
		f>>x1>>yy>>x2>>y2;
		g<<querry(1,1,n,0)<<'\n';
	}
}

void merge (int niv, int st, int dr)
{
	int i=st,p1=st,mij=(st+dr)/2;
	int p2=mij+1;
	while (p1<=mij && p2<=dr)
		if (arb[niv+1][p1]<arb[niv+1][p2])
			{arb[niv][i]=arb[niv+1][p1];i++;p1++;}
		else
			{arb[niv][i]=arb[niv+1][p2];i++;p2++;}
	if (p2<=dr)
		p1=p2;
	while (i<=dr)
			{arb[niv][i]=arb[niv+1][p1];p1++;i++;}
}

void build ( int k, int st, int dr, int niv)
{
	if (st==dr)
	{
		arb[niv][st]=y[st];
		return ;
	}
	int mij=(st+dr)/2;
	if (mij>=st) 
		build (2*k,st, mij,niv+1);
	if (mij<dr) 
		build (2*k+1,mij+1,dr,niv+1);
	merge (niv,st,dr);
}

void up (int l)
{
	while (l && (a[l]<a[l>>1]))
	{
		a[l]=(a[l]^a[l>>1])^(a[l>>1]=a[l]);
		b[l]=(b[l]^b[l>>1])^(b[l>>1]=b[l]);
		l>>=1;
	}
}

void coboara(int l)
{
	int x=l, y=1;
	while (x!=y)
	{
		x=y;
		if (2*x<=l && a[x]>a[2*x]) y=2*x;
		if (2*x+1<=l && (a[y]>a[2*x+1])) y=2*x+1;
		a[x]=(a[x]^a[y])^(a[y]=a[x]);
		b[x]=(b[x]^b[y])^(b[y]=b[x]);
	}
}

void sort()
{
	int i;
	for (i=1;i<=n;i++)
	{
		a[i]=x[i];
		b[i]=y[i];
		up(i);
	}
	for (i=1;i<=n;i++)
	{
		x[i]=a[1];
		y[i]=b[1];
		a[1]=a[n-i+1];
		b[1]=b[n-i+1];
		coboara(n-i);
	}
}

void readsort ()
{
	int i;
	f>>n;
	for (i=1;i<=n;i++)
		f>>x[i]>>y[i];
	sort();
}

int main()
{
	readsort();
	build(1,1,n,0);
	compute ();
	return 0;
}