Cod sursa(job #1026255)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 11 noiembrie 2013 14:04:48
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.43 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 16001
#define maxlog 16
#define filein "zoo.in"
#define fileout "zoo.out"
#define x first
#define y second
#define PII pair <int, int>
using namespace std;
PII a[maxn];
//int x[maxn],y[maxn],xa[maxn],ya[maxn];
int ys[maxn][maxlog],i,j,k,m,n,v,np,yi1,yi2,yinf,ysup;
void compute();
void sorty(int li,int ls,int niv)
{	if (ls-li>=1)
	{	for (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);
		k=li-1; i=li;
		m=(li+ls)>>1; j=m+1;
		while (i<=m && j<=ls)
		{	k++;
			if (ys[i][niv+1]<ys[j][niv+1]) {ys[k][niv]=ys[i][niv+1]; i++;}
			else {ys[k][niv]=ys[j][niv+1]; j++;}
		}
		while (i <= m) {ys[++k][niv]=ys[i][niv+1]; i++;}
		while (j<=ls) {ys[++k][niv]=ys[j][niv+1]; j++;}
	}
}
int main()
{	freopen(filein,"r",stdin);
	scanf("%ld",&n);
	for(i=1;i<=n;i++) scanf("%ld %ld",&a[i].x,&a[i].y);
	sort(a + 1, a + n + 1);
	for(i=1;i<=n;i++) ys[i][0]=a[i].y;
	sorty(1,n,0);
	compute();
	return 0;
}
void search(int ci,int cs,int li,int ls,int niv)
{
int mij;
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,i,j,k,p,li,ls,m;
int xa,ya,xb,yb,xi1,xi2,mi;

freopen(fileout,"w",stdout);

scanf("%ld",&nd);
for (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
      {
      /* the nice part */
      np=0;

      yinf=ya; ysup=yb;
      search(xa,xb,1,n,0);
      printf("%ld\n",np);
      }
    }
  }
}
/*
Varianta aleasa de autorul problemei consta intr-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).
*/