Cod sursa(job #1034338)

Utilizator thewildnathNathan Wildenberg thewildnath Data 17 noiembrie 2013 19:38:57
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;

#define NMAX 16002

struct punct
{
    int x,y;
};
int n,m,sol;
punct pc[NMAX],a,b;
vector <int> v[4*NMAX];

inline bool cmp(const punct &a,const punct &b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}


void build(int l,int r,int x)
{
    if(l==r)
    {
        v[x].push_back(l);
        return;
    }
    int med=(l+r)>>1,x1=(x<<1),x2=x1+1,nod;//,i,j;
    build(l,med,x1);
    build(med+1,r,x2);

    /*i=j=0;
    for(;i<v[x1].size() || j<v[x2].size();)
    {
        if(j==v[x2].size()-1 || (i<v[x1].size()-1 && pc[v[x1][i]].y < pc[v[x2][j]].y))
        {
            nod=v[x1][i];
            v[x].push_back(nod);
            ++i;
        }
        else
        {
            nod=v[x2][j];
            v[x].push_back(nod);
            ++j;
        }
    }*/
    vector <int>::iterator i,j;
    i=v[x1].begin();
    j=v[x2].begin();
    while(i!=v[x1].end() || j!=v[x2].end())
    {
        if(j==v[x2].end() || (i!=v[x1].end() && pc[*i].y<pc[*j].y))
        {
            v[x].push_back(*i);
            ++i;
        }
        else
        {
            v[x].push_back(*j);
            ++j;
        }
    }
}



inline void caut(int x)
{
    int s=0,d=v[x].size()-1,m,st,sf;
    while(s<=d)
    {
        m=(s+d)>>1;
        if(pc[v[x][m]].y>=a.y)
            d=m-1;
        else
            s=m+1;
    }
    st=s;

    s=0;d=v[x].size()-1;
    while(s<=d)
    {
        m=(s+d)>>1;
        if(pc[v[x][m]].y<=b.y)
            s=m+1;
        else
            d=m-1;
    }
    sf=d;

    sol+=(sf-st+1);
}




void query(int l,int r,int x)
{
    if(a.x<=pc[l].x && b.x>=pc[r].x)
    {
        caut(x);
        return;
    }
    if(l==r)
        return;
    int mij=(l+r)>>1,x1=(x<<1),x2=x1+x;

    if(a.x<=pc[mij].x)
        query(l,mij,x1);
    if(b.x>=pc[mij+1].x)
        query(mij+1,r,x2);

}


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

    scanf("%d",&n);
    for(i=1;i<=n;++i)
        scanf("%d%d",&pc[i].x,&pc[i].y);
    sort(pc+1,pc+1+n,cmp);

    build(1,n,1);




    scanf("%d",&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d%d%d",&a.x,&a.y,&b.x,&b.y);
        sol=0;
        query(1,n,1);
        printf("%d\n",sol);
    }





    return 0;
}