Cod sursa(job #615736)

Utilizator cnt_tstcont teste cnt_tst Data 10 octombrie 2011 18:29:40
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include<stdio.h>
#include<algorithm>
using namespace std;

#define pi pair<int,int>
#define x first
#define y second
#define LG 21
#define Nmax 16005

int A[LG][Nmax],n,m;
pi v[Nmax];

int aplic(int lev,int l,int r,int a,int b)
{
    int st,dr,s1,s2,mij;
    
    st=l;dr=r;s1=r+1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(a<=A[lev][mij])
        {
            dr=mij-1;
            s1=mij;
        }
        else
            st=mij+1;
    }
    if(s1==r+1)
        return 0;
        
    st=l;dr=r;s2=l-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(b>=A[lev][mij])
        {
            st=mij+1;
            s2=mij;
        }
        else
            dr=mij-1;
    }
    return s2-s1+1;
}

void build(int lev,int l,int r)
{
    if (l==r)
    {
        A[lev][l]=v[l].y;
        return ;
    }
    
    int mij=(l+r)/2;
    build(lev+1,l,mij);
    build(lev+1,mij+1,r);

    int st,dr,poz;

    st=l; dr=mij+1; poz=l;
    while(poz<=r)
    {
        if(dr>r || (st<=mij && A[lev+1][st]<=A[lev+1][dr]))
        {
            A[lev][poz]=A[lev+1][st];
            poz++; st++;
        }
        else
        {
            A[lev][poz]=A[lev+1][dr];
            poz++; dr++;
        }
    }
}

int query(int lev,int l,int r,pi a,pi b)
{
    if(a.x<=l && r<=b.x)
    {
        int sol=aplic(lev,l,r,a.y,b.y);
        return sol;
    }
    int mij=(l+r)/2,s1=0,s2=0;
    
    if(a.x<=mij)
        s1=query(lev+1,l,mij,a,b);
    if (b.x>mij)
        s2=query(lev+1,mij+1,r,a,b);        
    return s1+s2;
}

int main ()
{
    int i,st,dr,mij,sol=0;
    pi a,b;
    
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d%d",&v[i].x,&v[i].y);

    sort(v+1,v+n+1);
    build(1,1,n);

    scanf("%d",&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&a.x,&a.y,&b.x,&b.y);
        
        st=1;dr=n;sol=n+1;
        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[mij].x>=a.x)
            {
                sol=mij;
                dr=mij-1;
            }
            else
                st=mij+1;
        }
        a.x=sol;sol=0;
        st=1;dr=n;

        while(st<=dr)
        {
            mij=(st+dr)/2;
            if(v[mij].x<=b.x)
            {
                sol=mij;
                st=mij+1;
            }
            else
                dr=mij-1;
        }
        b.x=sol;
        
        int sol=0;
        if (a.x<=b.x)
            sol=query(1,1,n,a,b);
        printf("%d\n",sol);
    }
        
    return 0;
}