Cod sursa(job #71866)

Utilizator sealTudose Vlad seal Data 12 iulie 2007 00:02:39
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include<stdio.h>
#include<stdlib.h>
#define Nm (1<<15)
#define Mm (1<<17)
#define md ((l+r)>>1)
#define ls (n<<1)
#define rs (n<<1|1)
int *Y[Nm],Sol[Mm],n,m;
struct point
{
    int x,y;
} P[Nm];


void read()
{
    int i;

    freopen("zoo.in","r",stdin);
    scanf("%d",&n);
    for(i=0;i<n;++i)
        scanf("%d%d",&P[i].x,&P[i].y);
}

int cmp(const void *a, const void *b)
{
    return ((point*)a)->x-((point*)b)->x;
}

int i,j,k;

void build(int n, int l, int r)
{
    Y[n]=(int*)malloc((r-l+1)*sizeof(int));
    if(l==r)
        Y[n][0]=P[l].y;
    else
    {
        build(ls,l,md);
        build(rs,md+1,r);

        i=j=k=0;
        while(i<=md-l && j<r-md)
            if(Y[ls][i]<Y[rs][j])
                Y[n][k++]=Y[ls][i++];
            else
                Y[n][k++]=Y[rs][j++];
        while(i<=md-l)
            Y[n][k++]=Y[ls][i++];
        while(j<r-md)
            Y[n][k++]=Y[rs][j++];
    }
}

int bs1(int A[], int n, int v)
{
    int i,j,m;

    if(A[n-1]<v)
        return n;

    i=0; j=n-1;
    while(i<j)
    {
        m=(i+j)>>1;
        if(A[m]<v)
            i=m+1;
        else
            j=m;
    }
    return i;
}

int bs2(int A[], int n, int v)
{
    int i,j,m;

    if(A[0]>v)
        return -1;

    i=0; j=n-1;
    while(i<j)
    {
        m=(i+j+1)>>1;
        if(A[m]>v)
            j=m-1;
        else
            i=m;
    }
    return i;
}

int x1,y1,x2,y2,ans;

void query(int n, int l, int r)
{
    if(x1<=P[l].x && P[r].x<=x2)
        ans+=bs2(Y[n],r-l+1,y2)-bs1(Y[n],r-l+1,y1)+1;
    else
    {
        if(x1<=P[md].x)
            query(ls,l,md);
        if(x2>=P[md+1].x)
            query(rs,md+1,r);
    }
}

void solve()
{
    int i;

    qsort(P,n,sizeof(point),cmp);
    build(1,0,n-1);

    scanf("%d",&m);
    for(i=0;i<m;++i)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        ans=0;
        query(1,0,n-1);
        Sol[i]=ans;
    }
}

void write()
{
    int i;

    freopen("zoo.out","w",stdout);
    for(i=0;i<m;++i)
        printf("%d\n",Sol[i]);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}