Cod sursa(job #422687)

Utilizator mihaionlyMihai Jiplea mihaionly Data 23 martie 2010 08:06:42
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <cstdio>
using namespace std;
FILE *f=fopen("zoo.in","r");
FILE *g=fopen("zoo.out","w");
#define nmax 16005
int A[100][nmax],X[nmax];
struct punct
 {
 int x,y;
 };
punct P[nmax];
int n,m;
punct aux[nmax];
int X1,X2,Y1,Y2;
void msort(int l,int r)
 {
 if(l==r) return;
 int mij=(l+r)>>1;
 msort(l,mij);
 msort(mij+1,r);
 int i,j,k;
 for(k=l-1,i=l,j=mij+1;i<=mij||j<=r;)
  {
  if((i<=mij&&P[i].x<P[j].x)||j>r)
   aux[++k]=P[i++];
  else
   aux[++k]=P[j++];
  }
 for(i=l;i<=r;i++)
  P[i]=aux[i];
 }
void Build(int lv,int st,int dr)
 {
 if(st==dr)
  {
  A[lv][st]=P[st].y;
  return;
  }
 int mij=(st+dr)>>1;
 Build(lv+1,st,mij);
 Build(lv+1,mij+1,dr);
 int i,j,k;
 for(i=st,j=mij+1,k=st-1;i<=mij||j<=dr;)
  {
  if((i<=mij&&A[lv+1][i]<A[lv+1][j])||(j>dr))
   A[lv][++k]=A[lv+1][i++];
  else
   A[lv][++k]=A[lv+1][j++];
  }
 }
void read()
 {
 fscanf(f,"%d",&n);
 int i;
 for(i=1;i<=n;i++)
  fscanf(f,"%d %d",&P[i].x,&P[i].y);
 }
int cbin(int v,int l, int r,int a[])
{
    int i, step;
     
    for (step = 1; step <= (r-l)+1; step <<= 1);
     
    for (i = l-1; step; step >>= 1)  
        if (i + step <= r && a[i+step] <= v)
            i += step;
     
    return i;
}
int query(int lv,int st,int dr)
 {
 int ret=0,mij;
 if(st>=X1&&dr<=X2)
  {
  ret+=cbin(Y2,st,dr,A[lv])-cbin(Y1-1,st,dr,A[lv]);
  return ret;
  }
 mij=(st+dr)>>1;
 if(X1<=mij) ret+=query(lv+1,st,mij);
 if(X2>mij)  ret+=query(lv+1,mij+1,dr);
 return ret;
 }
int main()
 {
 read();
 msort(1,n);
 int i,sol;
 Build(1,1,n);
 fscanf(f,"%d",&m);
 for(i=1;i<=n;i++)
  X[i]=P[i].x;
 for(i=1;i<=m;i++)
  {
  fscanf(f,"%d %d %d %d",&X1,&Y1,&X2,&Y2);
  if(X2<X[1]||X1>X[n]) fprintf(g,"0\n");
  else
   {
   X1=cbin(X1-1,1,n,X)+1;
   X2=cbin(X2,1,n,X);
   sol=query(1,1,n);
   fprintf(g,"%d\n",sol);
   }
  }
 return 0;
 }