Cod sursa(job #1424150)

Utilizator heracleRadu Muntean heracle Data 23 aprilie 2015 17:04:54
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <cstdio>
#include <algorithm>

FILE* in=fopen("zoo.in","r");
FILE* out=fopen("zoo.out","w");

const int Q=16009,INF=2000000007;

int n;

struct point{
    int x,y;
} v[Q];

struct Nod{
    int st,dr;
    int val;

    Nod *a,*b;

    Nod()
    {
        a=NULL;
        b=NULL;
        val=0;
    }
} *radacina[Q];

int query(Nod *act, int st, int dr)
{
    if(act->dr<st || act->st>dr)
        return 0;
    if(act->st>=st && act->dr<=dr)
        return act->val;

    return query(act->a,st,dr)+query(act->b,st,dr);
}

int who(int x)
{
    int p=1<<14;
    int t=0;

    while(p)
    {
        if(p+t<=n && v[p+t].x<=x)
            t+=p;
        p/=2;
    }

    return t;
}

int dny[Q];

int find1(int x)
{
    int p=1<<14;
    int t=0;

    while(p)
    {
        if(p+t<=dny[0] && dny[p+t]<x)
            t+=p;
        p/=2;
    }
    return t;
}


void queries()
{
    int q;

    fscanf(in,"%d",&q);

    int a0,b0,a,b,d1,d2;

    for(int i=1; i<=q; i++)
    {
        fscanf(in,"%d%d%d%d",&d1,&a0,&d2,&b0);

        a=find1(a0);
        a++;

        b=find1(b0);

        if(dny[b+1]==b0)
            b++;

        d1--;
        d1=who(d1);
        d2=who(d2);

        fprintf(out,"%d\n",query(radacina[d2],a,b)-query(radacina[d1],a,b));
    }
}

Nod *down(Nod *act, Nod *alt, int poz)
{
    act=new Nod;
    act->st=alt->st;
    act->dr=alt->dr;
    act->val=alt->val+1;

    if(act->st==act->dr)
    {
        return act;
    }

    int md=act->st+act->dr;
    md/=2;

    if(poz<=md)
    {
        act->b=alt->b;
        act->a=down(act->a,alt->a, poz);
    }
    else
    {
        act->a=alt->a;
        act->b=down(act->b,alt->b,poz);
    }

    return act;
}

Nod *gen_start(Nod *act, int st, int dr)
{
    act=new Nod;
    act->st=st;
    act->dr=dr;

    if(st!=dr)
    {
        act->a=gen_start(act->a,st,(st+dr)/2);
        act->b=gen_start(act->b,(st+dr)/2+1,dr);
    }

    return act;
}


void main2()
{
    radacina[0]=gen_start(radacina[0],1,1<<14);

    for(int i=1; i<=n; i++)
    {
        radacina[i]=down(radacina[i],radacina[i-1],v[i].y);
    }

}

bool cmpx(const point &a, const point &b)
{
    return a.x<b.x;
}


bool cmpy(const point &a, const point &b)
{
    return a.y<b.y;
}


int main()
{
    fscanf(in,"%d",&n);

    for(int i=1; i<=n; i++)
    {
        fscanf(in,"%d%d",&v[i].x,&v[i].y);
    }
    std::sort(v+1,v+n+1,cmpy);

    int last=-INF,nxt=1;

    for(int i=1; i<=n; i++)
    {
        if(v[i].y==last)
        {
            v[i].y=v[i-1].y;
        }
        else
        {
            dny[nxt]=v[i].y;
            last=v[i].y;
            v[i].y=nxt++;
        }
    }
    dny[0]=nxt-1;

    std::sort(v+1,v+n+1,cmpx);

    main2();

    queries();

    return 0;
}