Cod sursa(job #1409332)

Utilizator gapdanPopescu George gapdan Data 30 martie 2015 14:43:37
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <cstdio>
#include <algorithm>
#define NMAX 20005

using namespace std;

int A[50][NMAX];
int X[NMAX], Y[NMAX],p[NMAX];
int xs,ys,xd,yd,n,m;

bool cmp(int r,int p)
{
    return (X[r] < X[p]);
}

void sorteaza(int st, int dr, int niv)
{
    int i,k,j;
    if (st == dr)
    {
        A[niv][st] = p[st];
        return;
    }

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

    //interclasez fii
    for(i = k = st,j = mij+1; i <= mij && j <= dr;)
    {
        if (Y[A[niv+1][i]] < Y[A[niv+1][j]])
            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++];
}

void constr_arb()
{
    for(int i = 1; i <= n; ++i) p[i] = i;
    sort(p+1,p+n+1,cmp);
    sorteaza(1,n,1);
}

int calc_sir(int ys,int yd,int st,int dr,int niv)
{
    int x,y;
    x = st-1, y = dr;
    while(x < y)
    {
        int mij = (x+y)/2;
        if (Y[A[niv][mij+1]] >= ys) y = mij;
            else x = mij +1;
    }

    int c = x;
    x = st,y = dr + 1;
    while(x < y)
    {
        int mij = (x+y)/2;
        if (Y[A[niv][mij]] <= yd)  x = mij+1;
            else y = mij;
    }
    return (x-c-1);
}


int calc_arb(int xs,int ys,int xd,int yd, int st, int dr, int niv)
{
    if (xs > X[p[dr]] || xd < X[p[st]]) return 0;

    if (xs <= X[p[st]] &&  X[p[dr]] <= xd)
        return calc_sir(ys,yd,st,dr,niv);

    int mij = (st+dr)/2;
    int val = calc_arb(xs,ys,xd,yd,st,mij,niv+1);
    val += calc_arb(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(int i = 1; i <= n; ++i)
        scanf("%d%d",&X[i],&Y[i]);

    constr_arb();
    scanf("%d",&m);
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d%d",&xs,&ys,&xd,&yd);
        printf("%d\n",calc_arb(xs,ys,xd,yd,1,n,1));
    }
    return 0;
}