Cod sursa(job #1587670)

Utilizator gapdanPopescu George gapdan Data 2 februarie 2016 14:23:36
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <cstdio>
#include <algorithm>
#define NMAX 100005

using namespace std;

int A[50][NMAX];
int n,m,xs,ys,xd,yd,i;
struct punct
{
    int x,y;
}v[NMAX];

bool cmp(punct r,punct p)
{
    return(r.x<p.x);
}

void constr_arb(int st,int dr,int niv)
{
    if(st == dr)
    {
        A[niv][st]=st;
        return;
    }

    int mij=(st+dr)/2;
    constr_arb(st,mij,niv+1);
    constr_arb(mij+1,dr,niv+1);

    //interclasam nivelele
    int i,j,k;
    i=st;j=mij+1;k=st;
    while(i <= mij && j <= dr)
    {
        if(v[A[niv+1][i]].y < v[A[niv+1][j]].y) A[niv][k++]=A[niv+1][i++];
            else A[niv][k++]=A[niv+1][j++];
    }

    while(i<=mij)
        A[niv][k++]=A[niv+1][i++];

    while(j<=dr)
        A[niv][k++]=A[niv+1][j++];

}

int calc(int ys,int yd,int st,int dr,int niv)
{
    int l,r;
    l=st-1;r=dr;
    while(l<r)
    {
        int mij=(l+r)/2;
        if(v[A[niv][mij+1]].y >= ys) r=mij;
            else l=mij+1;
    }

    int c=l;
    l=st;r=dr+1;
    while(l<r)
    {
        int mij=(l+r)/2;
        if(v[A[niv][mij]].y <=yd) l=mij+1;
            else r=mij;
    }
    return(l-c-1);
}

int query(int xs,int ys,int xd,int yd,int st,int dr,int niv)
{
    if(xs>v[dr].x || xd<v[st].x) return 0;
    if(xs<=v[st].x && v[dr].x<=xd)
        return calc(ys,yd,st,dr,niv);
    int mij=(st+dr)/2;
    int val=query(xs,ys,xd,yd,st,mij,niv+1);
    val+=query(xs,ys,xd,yd,mij+1,dr,niv+1);
    return val;
}

int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;++i) scanf("%d%d",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    constr_arb(1,n,1);
    scanf("%d",&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d%d",&xs,&ys,&xd,&yd);
        printf("%d\n",query(xs,ys,xd,yd,1,n,1));
    }
}