Cod sursa(job #25187)

Utilizator georgianaGane Andreea georgiana Data 4 martie 2007 11:17:53
Problema Ograzi Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 3.96 kb
#include <stdio.h>
#include <stdlib.h>

struct nod{
          int s, e;
          int *val;
          struct nod *st,*dr;
       };

int nroi,n,m,w,h,og[50001][2],oi[100001][2],i,j,poz,jos,sus;
char s[100];
struct nod *a;

void qSort(int st,int dr)
{
     int i=st, j=dr, m=oi[(i+j)/2][0];
     do
     {
         while (oi[i][0]<m) i++;
         while (oi[j][0]>m) j--;
         if (i<=j)
         {
             int aux=oi[i][0]; oi[i][0]=oi[j][0]; oi[j][0]=aux;
                 aux=oi[i][1]; oi[i][1]=oi[j][1]; oi[j][1]=aux;
             i++; j--;         
         }
     } 
     while (i<=j);
     if (st<j) qSort(st,j);
     if (i<dr) qSort(i,dr);
}

void create(struct nod *a, int start, int end)
{
     a->s=start;
     a->e=end;
     if (start==end)
       {
           a->val=(int*)malloc(sizeof(int));
           a->val[0]=1;
           a->val[1]=oi[start][1];
           a->st=NULL;
           a->dr=NULL;
       }
     else {
              int m=(start+end)/2;
              a->st=(struct nod *)malloc(sizeof(nod));
              create(a->st,start,m);
              a->dr=(struct nod *)malloc(sizeof(nod));
              create(a->dr,m+1,end);
              a->val=(int*)malloc(m*sizeof(int));
              a->val[0]=a->st->val[0]+a->dr->val[0];
              i=1,j=1,poz=1;
              while (i<=a->st->val[0] && j<=a->dr->val[0])
                 {
                     if (a->st->val[i]>a->dr->val[j])
                        {
                           a->val[poz++]=a->dr->val[j];
                           j++;
                        }
                     else {
                              a->val[poz++]=a->st->val[i];
                              i++;
                          }
                 }
              while (j<=a->dr->val[0])
                 {
                     a->val[poz++]=a->dr->val[j];
                     j++;
                 }
              while (i<=a->st->val[0])
                 {
                     a->val[poz++]=a->st->val[i];
                     i++;
                 }
          }
}

int min(int a, int b)
{
    if (a<b) return a;
    else return b;
}

int max(int a, int b)
{
    if (a>b) return a;
    else return b;
}

void find(struct nod *a, int start, int end)
{
     if (a->s==start && a->e==end)
        {
           int ss,dd;
           int st=1,dr=a->val[0];
           while (st<=dr)
              {
                  int m=(st+dr)/2;
                  if (a->val[m]>jos) { ss=m; dr=m-1; }
                  else st=m+1;
              }
           st=0,dr=a->val[0];
           while (st<=dr)
              {
                  int m=(st+dr)/2;
                  if (a->val[m]<sus) { dd=m; st=m+1; }
                  else dr=m-1;
              }
           nroi+=dd-ss+1;
           return;
        }
     if (start<=a->st->e) find(a->st,start,min(end,a->st->e));   
     if (end>=a->dr->s) find(a->dr,max(start,a->dr->s),end);   
}

int main()
{
    freopen("ograzi.in","r",stdin);
    scanf("%d %d %d %d",&n,&m,&w,&h);
    for (int i=0;i<n;i++)
       scanf("%d %d",&og[i][0],&og[i][1]);

    for (int i=0;i<m;i++)
       scanf("%d %d",&oi[i][0],&oi[i][1]);
    qSort(0,m-1);
    a=(struct nod *)malloc(sizeof(nod));
    create(a,0,m-1);
    
    nroi=0;
    for (int i=0;i<n;i++)
       {
           int ss,dd;
           int st=0,dr=m-1;
           while (st<=dr)
              {
                  int m=(st+dr)/2;
                  if (oi[m][0]>og[i][0]) { ss=m; dr=m-1; }
                  else st=m+1;
              }
           st=0,dr=m-1;
           while (st<=dr)
              {
                  int m=(st+dr)/2;
                  if (oi[m][0]<og[i][0]+w) { dd=m; st=m+1; }
                  else dr=m-1;
              }
           jos=og[i][1];
           sus=jos+h;
           find(a,ss,dd);
       }

    freopen("ograzi.out","w",stdout);
    printf("%d\n",nroi);
    fclose(stdout);
    return 0;
}