Cod sursa(job #25522)

Utilizator georgianaGane Andreea georgiana Data 4 martie 2007 12:49:54
Problema Ograzi Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 4.54 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[102];
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=a->val[0]+1,dd=0;
           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=1,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;
              }
           if (ss<=dd) 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);
    fgets(s,100,stdin);
    int cnt=0,poz=0;
    sscanf(s+poz,"%d%n",&n,&cnt);
    poz+=cnt;
    sscanf(s+poz,"%d%n",&m,&cnt);
    poz+=cnt;
    sscanf(s+poz,"%d%n",&w,&cnt);
    poz+=cnt;
    sscanf(s+poz,"%d%n",&h,&cnt);
    poz+=cnt;

    for (int i=0;i<n;i++)
       {
           fgets(s,100,stdin);
           cnt=0,poz=0;
           sscanf(s+poz,"%d%n",&og[i][0],&cnt);
           poz+=cnt;
           sscanf(s+poz,"%d%n",&og[i][1],&cnt);
           poz+=cnt;
       }

    for (int i=0;i<m;i++)
       {
           fgets(s,100,stdin);
           cnt=0,poz=0;
           sscanf(s+poz,"%d%n",&oi[i][0],&cnt);
           poz+=cnt;
           sscanf(s+poz,"%d%n",&oi[i][1],&cnt);
           poz+=cnt;
       }
    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;
}