Cod sursa(job #25467)

Utilizator moga_florianFlorian MOGA moga_florian Data 4 martie 2007 12:40:28
Problema Ograzi Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 2.68 kb
#include<stdio.h>
#define nmax 60000
#define logn 17

struct nod{int x, y;} p[nmax];
int n,m,h,w,x1,x2,y1,y2;
int x[nmax],t[logn][nmax],pt[logn][nmax][2];
int cx[nmax],cy[nmax];

void go(int niv,int l,int r)
{
int mij=(l+r)/2,i,j,k;
if(l==r)
   {
   t[niv][l]=p[l].y;
   return;     
   }     
go(niv+1,l,mij);
go(niv+1,mij+1,r);

//interclasarea
for(i=l,j=mij+1,k=l;i<=mij||j<=r;)
  if(j>r || (i<=mij && t[niv+1][i]<t[niv+1][j]) )
   {
   pt[niv][k][0]=i;
   pt[niv][k][1]=j-1;
   t[niv][k]=t[niv+1][i];
   k++;
   i++;
   }
  else
   {
   pt[niv][k][0]=i-1;
   pt[niv][k][1]=j;
   t[niv][k]=t[niv+1][j];
   k++;
   j++;       
   }
}

int searchx(int v)
{
int li=1,lf=m,mij;
if(x[1]>v) return 0;

while(lf-li>1)
 {
 mij=(li+lf)>>1;
 if(x[mij]<=v)
    li=mij;
 else
    lf=mij;    
 }
if(x[lf]<=v)
   return lf;
return li;   
}

int searcht(int v)
{
int li=1,lf=m,mij;
if(t[0][1]>v) return 0;

while(lf-li>1)
 {
 mij=(li+lf)>>1;
 if(t[0][mij]<=v)
    li=mij;
 else
    lf=mij;    
 }
if(t[0][lf]<=v)
   return lf;
return li;   
}

int query(int niv,int l,int r,int p1,int p2)
{
int mij,tr=0;
if(x1<=l && r<=x2)
  {
  if(p2<l || p1>r )
     return 0;
  if(p1<l && r<p2)
     return (r-l+1);
  if(t[niv][p1]==t[0][y1])
      p1--;
  tr=p2-p1;
  }
else
  {
  mij=(l+r)>>1;
  if(x1<=mij)
    tr+=query(niv+1,l,mij,pt[niv][p1][0],pt[niv][p2][0]);
  if(x2>mij)
    tr+=query(niv+1,mij+1,r,pt[niv][p1][1],pt[niv][p2][1]);  
  }
return tr;
}     

int main()
{
FILE *fin=fopen("ograzi.in","r"),
     *fout=fopen("ograzi.out","w");
     
fscanf(fin,"%d%d%d%d",&n,&m,&w,&h);
int i,j,k;
nod aux;
for(i=1;i<=n;i++)
  fscanf(fin,"%d%d",&cx[i],&cy[i]);
for(i=1;i<=m;i++)
  fscanf(fin,"%d%d",&p[i].x,&p[i].y);
  
//heap sortu
for(i=1;i<=m;i++)
   {
   j=i;
   while(j/2&& p[j/2].x<p[j].x) 
      {
      aux=p[j/2];
      p[j/2]=p[j];
      p[j]=aux;
      j/=2;       
      }              
   }
   
i=m;
while(i>1)
 {
 aux=p[1];
 p[1]=p[i];
 p[i]=aux;
 i--;
 
 j=1;
 while(1)
  {
  k=2*j;
  if(k>i) break;
  if(k+1<=i && p[k+1].x>p[k].x) k++;
  if(p[j].x >= p[k].x) break;
  
  aux=p[j];
  p[j]=p[k];
  p[k]=aux;
  j=k;
  }         
 }
 
//construirea arborelui
for(i=1;i<=m;i++)
  x[i]=p[i].x;
  
go(0,1,m);

int sol=0;
//queryuri
for(i=1;i<=n;i++)
  {
  x1=cx[i];y1=cy[i];
  x2=x1+w;y2=y1+h;
  
  if(x2<x[1] || x1>x[m] || y2<t[0][1] || y1>t[0][m]);
  else
    {
    x1=searchx(x1-1)+1;
    x2=searchx(x2);
    y1=searcht(y1-1)+1;
    y2=searcht(y2);
    
    sol+=query(0,1,m,y1,y2);
    }          
  }
  
fprintf(fout,"%d\n",sol);
fclose(fin);
fclose(fout);
return 0;    
}