Cod sursa(job #1001700)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 25 septembrie 2013 20:18:51
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.24 kb
#include <fstream>
#include <algorithm>
#include <assert.h>

using namespace std;

struct elem
{
    int val;
    int poz;
    int fel;
}xg[416015],yg[416015];

struct cord
{
    int x,y,poz,semn;
}v[46005],q[400005];

bool operator<(const cord &a,const cord &b)
{
    if(a.x<b.x)
        return 1;
    if(a.x==b.x)
        if(a.y<b.y)
            return 1;
    return 0;
}

bool operator<(const elem &a,const elem &b)
{
    if(a.val<b.val)
        return 1;
    if(a.val>b.val)
        return 0;
    if(a.fel<b.fel)
        return 1;
    return 0;
}

bool cmp(const elem &a,const elem &b)
{
    if(a.val<b.val)
        return 1;
    if(a.val>b.val)
        return 0;
    if(a.fel>b.fel)
        return 1;
    return 0;
}

int raspuns[400005];
int aib[1600005],n;

#define inf 2000000000
#define lsb(x) (x&(-x))


void update(int x,int val)
{
    int i;
    n*=8;
    for(i=x;i<=n;i+=lsb(i))
        aib[i]+=val;
    n/=8;
}

int sum(int x)
{
    int i,sum=0;
    for(i=x;i>0;i-=lsb(i))
        sum+=aib[i];
    return sum;
}

int main()
{
    ifstream cin("zoo.in");
    ofstream cout("zoo.out");

    int m=0,i,j,x[16005],y[16005],ante,next,xi[100005],yi[100005],xs[100005],ys[100005];
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];

        xg[i].val=x[i];
        xg[i].fel=0;
        xg[i].poz=i;

        yg[i].val=y[i];
        yg[i].fel=0;
        yg[i].poz=i;
    }

    cin>>m;
    for(i=1;i<=m;i++)
    {
        cin>>xi[i]>>yi[i]>>xs[i]>>ys[i];

        xg[n+(2*i)-1].val=xi[i];
        xg[n+(2*i)-1].poz=i;
        xg[n+(2*i)-1].fel=1;

        yg[n+(2*i)-1].val=yi[i];
        yg[n+(2*i)-1].poz=i;
        yg[n+(2*i)-1].fel=1;

        xg[n+(2*i)].val=xs[i];
        xg[n+(2*i)].poz=i;
        xg[n+(2*i)].fel=2;

        yg[n+(2*i)].val=ys[i];
        yg[n+(2*i)].poz=i;
        yg[n+(2*i)].fel=2;
    }
    xg[0].val=-inf;
    xg[0].fel=0;
    xg[0].poz=0;

    yg[0].val=-inf;
    yg[0].fel=0;
    yg[0].poz=0;

    xg[n+(2*m)+1].val=inf;
    xg[n+(2*m)+1].fel=0;
    xg[n+(2*m)+1].poz=0;

    yg[n+(2*m)+1].val=inf;
    yg[n+(2*m)+1].fel=0;
    yg[n+(2*m)+1].poz=0;

    sort(xg+1,xg+(n+2*m+1));
    sort(yg+1,yg+(n+2*m+1));

    ante=-inf;
    for(i=1;i<=(n+(2*m));i++)
        if(xg[i].fel==0)
            ante=xg[i].val;
        else if (xg[i].fel==2)
            xg[i].val=ante;

    ante=-inf;
    for(i=1;i<=(n+(2*m));i++)
    {
        if(yg[i].fel==0)
            ante=yg[i].val;
        else if(yg[i].fel==2)
            yg[i].val=ante;
    }

    sort(xg+1,xg+(n+2*m+1),cmp);
    sort(yg+1,yg+(n+2*m+1),cmp);


    next=inf;
    for(i=(n+(2*m));i>=1;i--)
    {
        if(xg[i].fel==0)
            next=xg[i].val;
        else if(xg[i].fel==1)
            xg[i].val=next;
    }

    next=inf;
    for(i=(n+(2*m));i>=1;i--)
    {
        if(yg[i].fel==0)
            next=yg[i].val;
        else if(yg[i].fel==1)
            yg[i].val=next;
    }
    ///////////////////////////

    int pred;
    int rasp=1;
    pred=xg[1].val;
    for(i=1;i<=(n+(2*m));i++)
    {
        if(xg[i].val!=pred)
        {
            pred=xg[i].val;
            rasp++;
        }
        if(xg[i].fel==0)
            x[xg[i].poz]=rasp;
        else if(xg[i].fel==1)
            xi[xg[i].poz]=rasp;
        else
            xs[xg[i].poz]=rasp;
    }
///////////////////////
    rasp=1;
    pred=yg[1].val;
    for(i=1;i<=(n+(2*m));i++)
    {
        if(yg[i].val!=pred)
        {
            pred=yg[i].val;
            rasp++;
        }
        if(yg[i].fel==0)
            y[yg[i].poz]=rasp;
        else if(yg[i].fel==1)
            yi[yg[i].poz]=rasp;
        else
            ys[yg[i].poz]=rasp;
    }
    /////////////////////////////////
    for(i=1;i<=n;i++)
    {
        v[i].x=x[i];
        v[i].y=y[i];
    }
    sort(v+1,v+n+1);
    for(j=1;j<=m;j++)
    {
        q[4*j-3].x=xs[j];
        q[4*j-3].y=ys[j];
        q[4*j-3].poz=j;
        q[4*j-3].semn=1;
        q[4*j-2].x=xs[j];
        q[4*j-2].y=yi[j]-1;
        q[4*j-2].poz=j;
        q[4*j-2].semn=-1;
        q[4*j-1].x=xi[j]-1;
        q[4*j-1].y=ys[j];
        q[4*j-1].poz=j;
        q[4*j-1].semn=-1;
        q[4*j].x=xi[j]-1;
        q[4*j].y=yi[j]-1;
        q[4*j].poz=j;
        q[4*j].semn=1;
    }

    sort(q+1,q+4*m+1); //ver dc n merg bine

    int vechi=0;
    vechi=v[1].x;

    j=1;
    while(j<=(4*m))
        if(q[j].x==0)
            j++;
        else
            break;

    for(i=1;i<=n;)
    {
        while(i<=n)
           if(v[i].x==vechi)
           {
              update(v[i].y,1);
              i++;
           }
           else
           {
                break;
           }
        while(j<=(4*m))
            if(q[j].x==vechi)
            {
                if(i<n && j==4*m)
                    assert(1);
                raspuns[q[j].poz]+=(sum(q[j].y)*q[j].semn);
                j++;
            }
            else
                break;
        vechi=v[i].x;
    }

    for(i=1;i<=m;i++)
    {
        //cout<<xi[i]<<' '<<xs[i]<<' '<<yi[i]<<' '<<ys[i]<<endl;
        cout<<raspuns[i]<<'\n';
    }
    cin.close();
    cout.close();
    return 0;
}