Cod sursa(job #483419)

Utilizator DraStiKDragos Oprica DraStiK Data 8 septembrie 2010 17:01:35
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <algorithm>
using namespace std;

#define mp make_pair
#define DIM 16005
#define sc second
#define fs first

pair <int,int> v[DIM];
int *aint[DIM<<2];
int n,m,nrt;

void read ()
{
    int i;

    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
        scanf ("%d%d",&v[i].fs,&v[i].sc);
}

void build (int nod,int st,int dr)
{
    int mij,nrc,ls,ld,i,j;

    aint[nod]=new int[dr-st+5];
    if (st==dr)
        aint[nod][0]=v[st].sc;
    else
    {
        mij=(st+dr)>>1;
        build (nod<<1,st,mij);
        build ((nod<<1)|1,mij+1,dr);
        nrc=0; ls=mij-st; ld=dr-mij-1;
        for (i=j=0; i<=ls || j<=ld; )
            if (i<=ls && (aint[nod<<1][i]<=aint[(nod<<1)|1][j] || j>ld))
                aint[nod][nrc++]=aint[nod<<1][i++];
            else
                aint[nod][nrc++]=aint[(nod<<1)|1][j++];
    }
}

void query (int nod,int st,int dr,int in,int sf,int y1,int y2)
{
    int mij;

    if (in<=st && dr<=sf)
        nrt+=upper_bound (aint[nod],aint[nod]+dr-st+1,y2)-lower_bound (aint[nod],aint[nod]+dr-st+1,y1);
    else
    {
        mij=(st+dr)>>1;
        if (in<=mij)
            query (nod<<1,st,mij,in,sf,y1,y2);
        if (mij<sf)
            query ((nod<<1)|1,mij+1,dr,in,sf,y1,y2);
    }
}

void solve ()
{
    int i,x1,x2,y1,y2,st,dr;

    sort (v+1,v+n+1);
    build (1,1,n);
    scanf ("%d",&m);
    for (i=1; i<=m; ++i)
    {
        scanf ("%d%d%d%d",&x1,&y1,&x2,&y2);
        st=lower_bound (v+1,v+n+1,mp (x1,y1))-v;
        dr=upper_bound (v+1,v+n+1,mp (x2,y2))-v-1;
        nrt=0;
        if (st<=dr)
            query (1,1,n,st,dr,y1,y2);
        printf ("%d\n",nrt);
    }
}

int main ()
{
    freopen ("zoo.in","r",stdin);
    freopen ("zoo.out","w",stdout);

    read ();
    solve ();

    return 0;
}