Cod sursa(job #25339)

Utilizator pauldbPaul-Dan Baltescu pauldb Data 4 martie 2007 12:04:39
Problema Ograzi Scor 40
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 2.01 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define maxn 300100
#define maxl 20
#define maxv 1000010

int n,m,dx,dy,sol;
int a[maxn],b[maxn],z[maxn],p[maxn],c[maxn];
int pos[maxv];
char v[maxl];

void read(int &x,int &y)
{
     fgets(v,maxl,stdin);
     x=y=0;
     
     int i=0;
     while (v[i]!=' ') x=x*10+v[i++]-'0';
     i++;
     while (v[i]!='\n') y=y*10+v[i++]-'0';
}

int cmp(int x,int y)
{
    return b[x]<b[y];
}

int cmp2(int x,int y)
{
    return (a[x]<a[y]) || ((a[x]==a[y]) && ((b[x]<b[y]) || ((b[x]==b[y]) && (z[x]<z[y]))));
}

int LSB(int x)
{
    return (x^(x-1))&x;
}

int query(int x)
{
     int rez=0;
     
     while (x>0)
     {
           rez+=c[x];
           x-=LSB(x);
     }
     
     return rez;
}

void update(int x)
{
     while (x<=n)
     {
           c[x]++;
           x+=LSB(x);
     }
}

int main()
{
    freopen("ograzi.in","r",stdin);
    freopen("ograzi.out","w",stdout);
    
    int i,aux,j;
    scanf("%d %d %d %d ",&aux,&m,&dx,&dy);
    
    for (i=1;i<=aux;i++)
    {
        n+=4;
        read(a[n],b[n]);
        a[n-1]=a[n];
        b[n-1]=b[n]+dy+1;
        a[n-2]=a[n]+dx+1;
        b[n-2]=b[n];
        a[n-3]=a[n]+dx+1;
        b[n-3]=b[n]+dy+1;
        z[n]=1;
        z[n-1]=2;
        z[n-2]=2;
        z[n-3]=1;
    }
    
    for (i=1;i<=m;i++)
    {
        n++;
        read(a[n],b[n]);
        a[n]++;
        b[n]++;
        z[n]=0;
    }
    
    for (i=1;i<=n;i++) p[i]=i;
    sort(p+1,p+n+1,cmp);
    
    aux=0;
    for (i=1;i<=n;)
    {
        aux++;
        pos[b[p[i]]]=aux;
        for (j=i+1;j<=n && b[p[i]]==b[p[j]];j++);
        i=j; 
    }
    
    for (i=1;i<=n;i++) p[i]=i;
    sort(p+1,p+n+1,cmp2);    
            
    for (i=1;i<=n;i++)
      if (z[p[i]]==0) update(pos[b[p[i]]]);
      else if (z[p[i]]==1) sol+=query(pos[b[p[i]]]);
           else sol-=query(pos[b[p[i]]]);
           
    printf("%d\n",sol);
    
    return 0;
}