Cod sursa(job #953066)

Utilizator primulDarie Sergiu primul Data 24 mai 2013 18:41:35
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 8.17 kb
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int semn,po,ras,s,ul,x1,y1,x2,y2,mij,p,u,nrx,nry,n,i,m11,x3[16009],y3[16009],x[16009],y[16009];
char sir[100];
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;
    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 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",&n);
for(i=1;i<=n;i++)
{
    //scanf("%d",&x[i]);
    //scanf("%d",&y[i]);
    po=1;
    gets(sir+1);
    ////////////////////////////////////////////////////////////////////////////////////
    semn=1;
    if(sir[po]=='-')
    {
        semn=-1;
        po++;
    }
    while(sir[po]>='0'&&sir[po]<='9')
    {
        x[i]=x[i]*10+sir[po]-48;
        po++;
    }
    x[i]*=semn;
    po++;
    ////////////////////////////////////////////////////////////////////////////////////
    semn=1;
    if(sir[po]=='-')
    {
        semn=-1;
        po++;
    }
    while(sir[po]>='0'&&sir[po]<='9')
    {
        y[i]=y[i]*10+sir[po]-48;
        po++;
    }
    y[i]*=semn;
    //////////////////////
    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\n",&m11);
while(m11)
{
    m11--;
/*    scanf("%d",&x1);
    scanf("%d",&y1);
    scanf("%d",&x2);
    scanf("%d",&y2);*/
    x1=y1=x2=y2=0;
    po=1;
    gets(sir+1);
    ////////////////////////////////////////////////////////////////////////////////////
    semn=1;
    if(sir[po]=='-')
    {
        semn=-1;
        po++;
    }
    while(sir[po]>='0'&&sir[po]<='9')
    {
        x1=x1*10+sir[po]-48;
        po++;
    }
    x1*=semn;
    po++;
    ////////////////////////////////////////////////////////////////////////////////////
    semn=1;
    if(sir[po]=='-')
    {
        semn=-1;
        po++;
    }
    while(sir[po]>='0'&&sir[po]<='9')
    {
        y1=y1*10+sir[po]-48;
        po++;
    }
    y1*=semn;
    po++;
    ////////////////////////////////////////////////////////////////////////////////////
    semn=1;
    if(sir[po]=='-')
    {
        semn=-1;
        po++;
    }
    while(sir[po]>='0'&&sir[po]<='9')
    {
        x2=x2*10+sir[po]-48;
        po++;
    }
    x2*=semn;
    po++;
    ////////////////////////////////////////////////////////////////////////////////////
    semn=1;
    if(sir[po]=='-')
    {
        semn=-1;
        po++;
    }
    while(sir[po]>='0'&&sir[po]<='9')
    {
        y2=y2*10+sir[po]-48;
        po++;
    }
    y2*=semn;
    po++;
    ////////////////////////////////////////////////////////////////////////////////////
    if(x2<x3[1]||y2<y3[1])
    {
        printf("0\n");
        continue;
    }
    if(x1>x3[nrx]||y1>y3[nry])
    {
        printf("0\n");
        continue;
    }
    if(x2>=x3[nrx]&&x1<=x3[1]&&y1<=y3[1]&&y2>=y3[nry])
    {
        printf("%d\n",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!");*/
    /*a1=x1;
    while(x3[x1])*/
    s=0;
    query(1,1,nrx,x1,x2,y1,y2);
    printf("%d\n",s);
}
return 0;
}