Cod sursa(job #1026650)

Utilizator enedumitruene dumitru enedumitru Data 11 noiembrie 2013 20:44:51
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.65 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;
}
/*
	Construim un arbore de intervale, care permite determinarea numarului de puncte din interiorul unui dreptunghi
	cu o complexitate O(logN*logN).
	Astfel, se sorteaza coordonatele x ale punctelor si se construieste un arbore de intervale. 
	Primul nivel al arborelui va contine toate coordonatele x.
	Cei doi fii ai lui vor contine prima jumatate, respectiv a doua jumatate a punctelor (sortate dupa coordonata x) s.a.m.d.
	Intervalele de pe ultimul nivel al arborelui contin cate un singur punct. In total, vor exista aproximativ 2N noduri in arbore.
	Pentru fiecare interval de coordonate x, se mentin sortate coordonatele y corespunzatoare punctelor
	care au coordonatele x in intervalul respectiv. 
	Astfel, memoria folosita este O(N*logN).
	Pentru fiecare dreptunghi, se executa cautarea in arborele de intervale pentru segmentul (x1,x2). 
	Acest segment se imparte, pornind de la radacina pana spre ultimul nivel, in segmente mai mici,
	pana cand segmentul la care s-a ajuns se suprapune perfect peste intervalul la care s-a ajuns.
	Se poate demonstra usor ca vor fi "atinse" O(logN) intervale din arbore.
	Pentru fiecare interval din arbore, se executa o cautare binara intre coordonatele y
	corespunzatoare coordonatelor x din acel interval,
	pentru a determina cate puncte din intervalul respectiv se afla in intervalul [y1,y2] (adica in interiorul dreptughiului).
*/