Cod sursa(job #88640)

Utilizator mugurelionutMugurel-Ionut Andreica mugurelionut Data 3 octombrie 2007 11:50:29
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.19 kb
/* Mugurel Ionut Andreica - Bucuresti, ROMANIA */

/* Time Complexity: O(logN*logN) for every query */

#include <stdio.h>
#include <string.h>
#define maxn 16001
#define maxlog 16
#define filein "zoo.in"
#define fileout "zoo.out"

long x[maxn],y[maxn],xa[maxn],ya[maxn];
long ys[maxn][maxlog],i,j,k,m,n,v,np,yi1,yi2,yinf,ysup;

void read();
void sortx(long,long);
void sorty(long,long,long);
void precompute();
void compute();

int main()
{
read();
precompute();
compute();
return 0;
}

void read()
{
long i;
freopen(filein,"r",stdin);
scanf("%ld",&n);

for (i=1;i<=n;i++)
  scanf("%ld %ld",&x[i],&y[i]);
}

void sortx(long li,long ls)
{
if (ls-li==1)
  {
  if (x[ls]<x[li])
    {
    v=x[ls]; x[ls]=x[li]; x[li]=v;
    v=y[ls]; y[ls]=y[li]; y[li]=v;
    }
  }
else
if (ls-li>1)
  {
  sortx(li,(li+ls)>>1);
  sortx(((li+ls)>>1)+1,ls);

  k=li-1;
  i=li;
  m=(li+ls)>>1;
  j=m+1;

  while (i<=m && j<=ls)
    {
    k++;

    if (x[i]<x[j])
      {
      xa[k]=x[i]; ya[k]=y[i];
      i++;
      }
    else
      {
      xa[k]=x[j]; ya[k]=y[j];
      j++;
      }
    }

  if (i<=m)
    {
    for (j=i;j<=m;j++)
      {
      k++;
      xa[k]=x[j]; ya[k]=y[j];
      }
    }
  else
    {
    for (i=j;i<=ls;i++)
      {
      k++;
      xa[k]=x[i]; ya[k]=y[i];
      }
    }

  for (k=li;k<=ls;k++)
    {
    x[k]=xa[k]; y[k]=ya[k];
    }
  }
}

void sorty(long li,long ls,long 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++;
      }
    }

  if (i<=m)
    {
    for (j=i;j<=m;j++)
      {
      k++;
      ys[k][niv]=ys[j][niv+1];
      }
    }
  else
    {
    for (i=j;i<=ls;i++)
      {
      k++;
      ys[k][niv]=ys[i][niv+1];
      }
    }
  }
}

void precompute()
{
long i;

sortx(1,n);
for (i=1;i<=n;i++)
  ys[i][0]=y[i];

sorty(1,n,0);
}

void search(long ci,long cs,long li,long ls,long niv)
{
long 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()
{
long nd,i,j,k,p,li,ls,m;
long 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>x[n] || xb<x[1])
    printf("0\n");
  else
    {
    if (xa<x[1]) xa=1;
    else
      {
      li=1; ls=n; xi1=n+1;
      while (li<=ls)
        {
        mi=(li+ls)>>1;

        if (x[mi]<xa)
          li=mi+1;
        else
          {
          xi1=mi;
          ls=mi-1;
          }
        }
      xa=xi1;
      }

    if (xb>x[n]) xb=n;
    else
      {
      li=1; ls=n; xi2=0;
      while (li<=ls)
        {
        mi=(li+ls)>>1;

        if (x[mi]>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);
      }
    }
  }
}