Cod sursa(job #29416)

Utilizator devilkindSavin Tiberiu devilkind Data 9 martie 2007 12:38:37
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.92 kb
#include <stdio.h>
#include <stdlib.h>
#define INFINIT -2000000002
#define NMAX 16001

FILE *f = fopen("zoo.in","rt"), *g = fopen("zoo.out","wt");

struct point{long int x,y;};

point a[15][NMAX];

long int n,i,j,k,st,dr,mid,pct[NMAX][2],ord[NMAX],pnt[NMAX][2],x1,x2,y1,y2,m;
long int arb[NMAX*3][2];

int cmp(const void *x, const void *y)
{return pct[ * (long int *) x ][0] - pct[ * (long int *) y ][0];
}

void citire()
{
fscanf(f,"%ld",&n);
for (i=1;i<=n;i++)
    {fscanf(f,"%ld %ld",&pct[i][0],&pct[i][1]);
    ord[i]=i;}
pct[0][0]=INFINIT;
pct[0][1]=INFINIT;
qsort(ord,n+1,sizeof(long int),cmp);
for (i=1;i<=n;i++)
    {pnt[i][0]=pct[ord[i]][0];
    pnt[i][1]=pct[ord[i]][1];}
}

void build(long int nod,long int dpth, long int st, long int dr)
{
long int x,y;
if (st==dr) {a[dpth][st].x=pnt[st][0];
            a[dpth][st].y=pnt[st][1];
            arb[nod][0]=pnt[st][0];
            arb[nod][1]=pnt[st][0];
            }
            else 
            {
            arb[nod][0]=pnt[st][0];
            arb[nod][1]=pnt[dr][0];
            long int mid;
            mid=(st+dr)/2;
            build(nod*2,dpth+1,st,mid);
            build(nod*2+1,dpth+1,mid+1,dr);
            x=st;
            y=mid+1;
            i=st;
	    while (i<=dr&&x<=mid&&y<=dr)
                  {
                  if (a[dpth+1][x].y<a[dpth+1][y].y) {a[dpth][i]=a[dpth+1][x];x++;}
                                                     else {a[dpth][i]=a[dpth+1][y];y++;}
                  i++;
                  }
            if (x<=mid) for (;x<=mid;x++)
                            a[dpth][i++]=a[dpth+1][x];
		       else for (;y<=dr;y++)
			       a[dpth][i++]=a[dpth+1][y];
            }
}                      

long int nr;

long int srch(long int val,long int dpth,long int s,long int d)
{
long int st,dr,mid;
st=s-1;
dr=d;
mid=(st+dr)/2;
while (st<dr-1)    
      {
      if (a[dpth][mid].y<=val) st=mid;
         else dr=mid;
      mid=(st+dr)/2;
      }
if (a[dpth][dr].y<=val) return dr;
return st;
}


void query(long int nod,long int dpth, long int st, long int dr, long int x1, long int x2)
{long int r1,r2,mid;
if (x1<=arb[nod][0]&&arb[nod][1]<=x2) {r1=srch(y1-1,dpth,st,dr);
                                           r2=srch(y2,dpth,st,dr);                
                                           nr=nr+r2-r1;
                                           }
   else if ((arb[nod][0]<=x1&&x1<=arb[nod][1])||(arb[nod][0]<=x2&&x2<=arb[nod][1]))
        {mid=(st+dr)/2;
        query(nod*2,dpth+1,st,mid,x1,x2);
        query(nod*2+1,dpth+1,mid+1,dr,x1,x2);
        }
}  
                  
void answer()
{
fscanf(f,"%ld",&m);
for (i=1;i<=m;i++)
    {
    fscanf(f,"%ld %ld %ld %ld",&x1,&y1,&x2,&y2);
    nr=0;
    query(1,1,1,n,x1,x2);
    fprintf(g,"%ld\n",nr);
    }   
}
            

int main()
{
citire();
build(1,1,1,n);
answer();
fclose(f);
fclose(g);
return 0;
}