Cod sursa(job #1551470)

Utilizator pepsiM4A1Ozturk Arif pepsiM4A1 Data 15 decembrie 2015 22:07:58
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.4 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
struct s
{
    int x;
    int y;
}a[16023];
struct arbore
{
    vector<int>v;
    bool vis;
}arb[64023];
int n,sum;
int comp(s a,s b)
{
    return a.x<b.x;
}
int ver(int nod)
{
    if(arb[2*nod].vis==1&&arb[2*nod+1].vis==1) return 1;
    return 0;
}
void interclas(int nod)
{
    int f1=2*nod,f2=f1+1;
    int m1=arb[f1].v.size(),m2=arb[f2].v.size(),p1=0,p2=0;
    while(1)
    {
        if(p1==m1&&p2==m2) return;
        else if(p1==m1)
        {
            arb[nod].v.push_back(arb[f2].v[p2]);
            ++p2;
        }
        else if(p2==m2)
        {
            arb[nod].v.push_back(arb[f1].v[p1]);
            ++p1;
        }
        else if(arb[f1].v[p1]<arb[f2].v[p2])
        {
            arb[nod].v.push_back(arb[f1].v[p1]);
            ++p1;
        }
        else
        {
            arb[nod].v.push_back(arb[f2].v[p2]);
            ++p2;
        }
    }
}
void update(int s,int e,int pos,int val,int nod)
{
    if(s==e) arb[nod].v.push_back(val);
    else
    {
        int mij=(s+e)/2;
        if(pos<=mij) update(s,mij,pos,val,2*nod);
        else update(mij+1,e,pos,val,2*nod+1);
        if(arb[2*nod].v.size()!=0&&arb[2*nod+1].v.size()!=0) interclas(nod);
    }
}
int findcoord1(int nr)
{
    int s=1,e=n,rasp=0;
    while(s<=e)
    {
        int mij=(s+e)/2;
        if(a[mij].x>=nr)
        {
            rasp=mij;
            e=mij-1;
        }
        else s=mij+1;
    }
    return rasp;
}
int findcoord2(int nr)
{
    int s=1,e=n,rasp=0;
    while(s<=e)
    {
        int mij=(s+e)/2;
        if(a[mij].x<=nr)
        {
            rasp=mij;
            s=mij+1;
        }
        else e=mij-1;
    }
    return rasp;
}
void query(int s,int e,int p1,int p2,int q1,int q2,int nod)
{
    if(s==p1&&e==p2)
    {
        int inc=0,sf=arb[nod].v.size()-1,r1=sf+1,r2=-1;
        while(inc<=sf)
        {
            int mij=(inc+sf)/2;
            if(q1<=arb[nod].v[mij])
            {
                r1=mij;
                sf=mij-1;
            }
            else inc=mij+1;
        }
        inc=0,sf=arb[nod].v.size()-1;
        while(inc<=sf)
        {
            int mij=(inc+sf)/2;
            if(q2>=arb[nod].v[mij])
            {
                r2=mij;
                inc=mij+1;
            }
            else sf=mij-1;
        }
        //printf("%d %d\n",r1,r2);
        sum+=(r2-r1+1);
    }
    else
    {
        int mij=(s+e)/2;
        if(p2<=mij) query(s,mij,p1,p2,q1,q2,2*nod);
        else if(p1>mij) query(mij+1,e,p1,p2,q1,q2,2*nod+1);
        else
        {
            query(s,mij,p1,mij,q1,q2,2*nod);
            query(mij+1,e,mij+1,p2,q1,q2,2*nod+1);
        }
    }
}
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",&a[i].x,&a[i].y);
    sort(a+1,a+n+1,comp);
    for(int i=1;i<=n;i++) update(1,n,i,a[i].y,1);
    int x1,y1,x2,y2,m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        x1=findcoord1(x1),x2=findcoord2(x2);
      //  printf("%d %d\n",x1,x2);
        if(x1>x2)
        {
            printf("0\n");
            continue;
        }
        if(x1==0) x1=1;
        sum=0,query(1,n,x1,x2,y1,y2,1);
        printf("%d\n",sum);
    }
}