Cod sursa(job #906587)

Utilizator geniucosOncescu Costin geniucos Data 6 martie 2013 22:07:49
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 6.14 kb
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int ras,s,ul,x1,y1,x2,y2,mij,p,u,nrx,nry,n,i,m11,x3[16009],y3[16009],x[1609],y[16009];
vector < int > arb[64009],vyy[16009];
vector < pair < int , int > > v1,v2;
vector < pair < int , int > > ::iterator it;
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        int i;
        //arb[nod].push_back(y[st]);
        sort(vyy[st].begin(),vyy[st].end());
        for(i=0;i<vyy[st].size();i++)
            arb[nod].push_back(vyy[st][i]);
        return ;
    }
    int mij=(st+dr)>>1,nod1,nod2,i1,i2;
    build(nod<<1,st,mij);
    build((nod<<1)+1,mij+1,dr);
    nod1=(nod<<1);
    nod2=(nod<<1)+1;
    i1=0;
    i2=0;
    while(i1<arb[nod1].size()&&i2<arb[nod2].size())
    {
        if(arb[nod1][i1]<arb[nod2][i2])
        {
            arb[nod].push_back(arb[nod1][i1]);
            i1++;
        }
        else
        {
            arb[nod].push_back(arb[nod2][i2]);
            i2++;
        }
    }
    for(i1=i1;i1<arb[nod1].size();i1++)
        arb[nod].push_back(arb[nod1][i1]);
    for(i2=i2;i2<arb[nod2].size();i2++)
        arb[nod].push_back(arb[nod2][i2]);
    return ;
}
int sumpeinterv(int nod,int y1,int y2)
{
    int ras,p,u,mij,stanga,dreapta,nr1=0;
    if(arb[nod].empty()) return 0;
    if(y1>arb[nod][arb[nod].size()-1]) return 0;
    if(y2<arb[nod][0]) return 0;
    if(y2>arb[nod][arb[nod].size()-1]&&y1<arb[nod][0]) arb[nod].size();
    /*for(i=0;i<arb[nod].size();i++)
        if(arb[nod][i]>=y1&&arb[nod][i]<=y2) nr1++;
    return nr1;*/
    p=0;
    u=arb[nod].size()-1;
    ras=-1;
    while(p<=u)
    {
        mij=(p+u)>>1;
        if(arb[nod][mij]>y1) u=mij-1;
        else
        if(arb[nod][mij]<y1)
        {
            ras=mij;
            p=mij+1;
        }
        else break;
    }
    if(p<=u)
    {
        while(arb[nod][mij]==y1) mij--;
        stanga=mij;
    }
    else
    {
        //while(arb[nod][p]>=y1&&p>=0) p--;
        stanga=ras;
    }
    ///////////////////////////////////////////////////////////////////////////////////
    p=0;
    u=arb[nod].size()-1;
    ras=u;
    while(p<=u)
    {
        mij=(p+u)>>1;
        if(arb[nod][mij]>y2) u=mij-1;
        else
        if(arb[nod][mij]<y2)
        {
            ras=mij;
            p=mij+1;
        }
        else break;
    }
    if(p<=u)
    {
        while(arb[nod][mij]==y2) mij++;
        dreapta=mij-1;
    }
    else
    {
        dreapta=ras;
    }
    return dreapta-stanga;
}
void query(int nod,int st,int dr,int x1,int x2,int y1,int y2)
{
    if(st>=x1&&dr<=x2)
    {
        s+=sumpeinterv(nod,y1,y2);
        return ;
    }
    int mij=(st+dr)>>1;
    if(x1<=mij)
        query(nod<<1,st,mij,x1,x2,y1,y2);
    if(x2>mij)
        query((nod<<1)+1,mij+1,dr,x1,x2,y1,y2);
    return ;
}
int main()
{
freopen("zoo.in","r",stdin);
freopen("zoo.out","w",stdout);
scanf("%d",&n);
for(i=1;i<=n;i++)
{
    scanf("%d",&x[i]);
    scanf("%d",&y[i]);
    v1.push_back(make_pair(x[i],i));
    v2.push_back(make_pair(y[i],i));
}
sort(v1.begin(),v1.end());
ul=v1.begin()->first-1;
x3[0]=ul;
for(it=v1.begin();it!=v1.end();it++)
{
    if(it->first!=ul)
    {
        ul=it->first;
        nrx++;
        x3[nrx]=it->first;
    }
    x[it->second]=nrx;
}
////////////////////////////////////////////
sort(v2.begin(),v2.end());
ul=v2.begin()->first-1;
y3[0]=ul;
for(it=v2.begin();it!=v2.end();it++)
{
    if(it->first!=ul)
    {
        ul=it->first;
        nry++;
        y3[nry]=it->first;
    }
    y[it->second]=nry;
}
////////////////////////////////////////////
for(i=1;i<=n;i++)
    vyy[x[i]].push_back(y[i]);
build(1,1,nrx);
////////////////////////////////////////////
scanf("%d",&m11);
while(m11)
{
    m11--;
    scanf("%d",&x1);
    scanf("%d",&y1);
    scanf("%d",&x2);
    scanf("%d",&y2);
    if(x2<x3[1]||y2<y3[1])
    {
        printf("0\n");
        continue;
    }
    if(x1>x3[nrx]||y1>y3[nry])
    {
        printf("0\n");
        continue;
    }
    //////////////////////////////
    p=1;
    u=nrx;
    while(p<=u)
    {
        mij=(p+u)>>1;
        if(x3[mij]>x1)
        {
            ras=mij;
            u=mij-1;
        }
        else
        if(x3[mij]<x1) p=mij+1;
        else break;
    }
    if(p<=u) x1=mij;
    else x1=ras;
    //////////////////////////////
    p=1;
    u=nry;
    while(p<=u)
    {
        mij=(p+u)>>1;
        if(y3[mij]>y1)
        {
            ras=mij;
            u=mij-1;
        }
        else
        if(y3[mij]<y1) p=mij+1;
        else break;
    }
    if(p<=u) y1=mij;
    else y1=ras;
    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////
    //////////////////////////////
    p=1;
    u=nrx;
    while(p<=u)
    {
        mij=(p+u)>>1;
        if(x3[mij]>x2) u=mij-1;
        else
        if(x3[mij]<x2)
        {
            p=mij+1;
            ras=mij;
        }
        else break;
    }
    if(p<=u) x2=mij;
    else x2=ras;
    //////////////////////////////
    p=1;
    u=nry;
    while(p<=u)
    {
        mij=(p+u)>>1;
        if(y3[mij]>y2) u=mij-1;
        else
        if(y3[mij]<y2)
        {
            ras=mij;
            p=mij+1;
        }
        else break;
    }
    if(p<=u) y2=mij;
    else y2=ras;
    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    //////////////////////////////
    if(x1==0) x1++;
    if(x2==0)
    {
        printf("0\n");
        continue;
    }
/*    for(i=1;i<arb[1].size();i++)
        if(arb[1][i]<arb[1][i-1]) printf("Nu-i bun arborele!");*/
    s=0;
    query(1,1,nrx,x1,x2,y1,y2);
    printf("%d\n",s);
}
return 0;
}