Cod sursa(job #1026655)

Utilizator enedumitruene dumitru enedumitru Data 11 noiembrie 2013 20:49:52
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
#include <cstdio>
#include <algorithm>
#define x first
#define y second
#define PII pair <int, int>
using namespace std;
PII a[16001];
int ys[16001][16];
int n,np,yinf,ysup;
void sorty(int li, int ls, int niv)
{	if(ls>=li+1)
	{	for(int i=li;i<=ls;i++) ys[i][niv+1]=ys[i][niv];
		sorty(li,(li+ls)>>1,niv+1);
		sorty(((li+ls)>>1)+1,ls,niv+1);
		int k=li-1, i=li, m=(li+ls)>>1, j=m+1;
		while(i<=m && j<=ls)
			if(ys[i][niv+1]<ys[j][niv+1]) ys[++k][niv]=ys[i++][niv+1];
				else ys[++k][niv]=ys[j++][niv+1];
		while(i<=m) ys[++k][niv]=ys[i++][niv+1];
		while(j<=ls) ys[++k][niv]=ys[j++][niv+1];
	}
}
void search(int ci, int cs, int li, int ls, int niv)
{	int mij,yi1,yi2;
	if(li==ls) {if(ys[li][niv]>=yinf && ys[li][niv]<=ysup) np++;}
	else if(ls>li)
		  {	if(ci==li && cs==ls)
			{	yi1=ls+1;
				while(li<=ls)
				{	mij=(li+ls)>>1;
					if(ys[mij][niv]<yinf) li=mij+1; else {yi1=mij; ls=mij-1;}
				}
				li=ci; ls=cs; yi2=li-1;
				while(li<=ls)
				{	mij=(li+ls)>>1;
					if(ys[mij][niv]>ysup) ls=mij-1; else {yi2=mij; li=mij+1;}
				}	
				if(yi1<=yi2) np+=(yi2-yi1+1);
			}
			else
			{	mij=(li+ls)>>1;
				if(ci<=mij)
					{	if (cs<=mij) search(ci,cs,li,mij,niv+1);
							else
							{	search(ci,mij,li,mij,niv+1);
								search(mij+1,cs,mij+1,ls,niv+1);
							}
					}
				else search(ci,cs,mij+1,ls,niv+1);
			}
		  }
}
void compute()
{	int nd,li,ls,xa,ya,xb,yb,xi1,xi2,mi;
	freopen("zoo.out","w",stdout);
	scanf("%ld",&nd);
	for(int k=1;k<=nd;k++)
	{	scanf("%ld %ld %ld %ld",&xa,&ya,&xb,&yb);
		if(xa>a[n].x || xb<a[1].x) printf("0\n");
		else
		{	if(xa<a[1].x) xa=1;
			else
			{	li=1; ls=n; xi1=n+1;
				while(li<=ls)
				{	mi=(li+ls)>>1;
					if(a[mi].x<xa) li=mi+1; else {xi1=mi; ls=mi-1;}
				}
				xa=xi1;
			}
			if (xb>a[n].x) xb=n;
			else
			{	li=1; ls=n; xi2=0;
				while(li<=ls)
				{	mi=(li+ls)>>1;
					if(a[mi].x>xb) {ls=mi-1;} else {xi2=mi; li=mi+1;}
				}
				xb=xi2;
			}
			if(xa>xb) printf("0\n");
			else
			{	np=0; yinf=ya; ysup=yb;
				search(xa,xb,1,n,0);
				printf("%ld\n",np);
			}
		}
	}
}
int main()
{	freopen("zoo.in","r",stdin);
	scanf("%ld",&n);
	for(int i=1;i<=n;i++) scanf("%ld %ld",&a[i].x,&a[i].y);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) ys[i][0]=a[i].y;
	sorty(1,n,0);
	compute();
	return 0;
}