Cod sursa(job #2523534)

Utilizator toadehuPuscasu Razvan Stefan toadehu Data 14 ianuarie 2020 12:22:04
Problema Zoo Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.22 kb
#include <bits/stdc++.h>

using namespace std;

int n,m;
int nr=0,ans[100069];

struct trie
{
    int val;
    trie* fii[2];
};
trie* t = new trie();

struct punct
{
    int x,y;
} v[16009];

bool acomp1 (punct a,punct b)
{
    return a.x<b.x;
}

struct intrebari
{
    int x,y1,y2,ind;
} query[200009];

bool acomp2 (intrebari a,intrebari b)
{
    return a.x<b.x;
}

int cauta (unsigned int st,unsigned int dr,unsigned int in, unsigned int sf,trie* nod)
{
    if (st==in && dr==sf)
    {
        return nod->val;
    }
    unsigned int mij=(st+dr)/2;
    if (mij<st)
    {
        if (nod -> fii[1] == NULL)
        {
            return 0;
        }
        return cauta(mij+1,dr,mij+1,sf,nod->fii[1]);
    }
    if (mij>=dr)
    {
        if (nod -> fii[0] == NULL)
        {
            return 0;
        }
        return cauta(st,mij,in,mij,nod->fii[1]);
    }
    int x=0;
    if (nod -> fii[0] != NULL)
    {
        x=cauta(st,mij,in,mij,nod->fii[0]);
    }
    if (nod -> fii[1] != NULL)
    {
        x+=cauta(mij+1,dr,mij+1,dr,nod->fii[1]);
    }
    return x;
}

void update (unsigned int st,unsigned int dr,unsigned val,trie* nod)
{
    if (st==dr)
    {
        nod -> val++;
        return;
    }
    int mij=(st+dr)/2;
    if (mij>=val)
    {
        if (nod -> fii[0] != NULL)
        {
            update(st,mij,val,nod -> fii[0]);
        }
        else
        {
            nod -> fii[0] = new trie();
        }
    }
    else
    {
        if (nod -> fii[1]==NULL)
        {
            nod -> fii[1] = new trie();
        }
        update (mij+1,dr,val,nod -> fii[1]);
    }
    int x=0;
    if (nod -> fii[0] != NULL)
    {
        x = nod -> fii[0] -> val;
    }
    if (nod -> fii[1] != NULL)
    {
        x+= nod -> fii[1] -> val;
    }
    nod -> val = x;
}

int main()
{
    ifstream fin ("zoo.in");
    ofstream fout ("zoo.out");
    fin>>n;
    for (int i=1; i<=n; ++i)
    {
        fin>>v[i].x>>v[i].y;
    }
    sort(v+1,v+n+1,acomp1);
    fin>>m;
    for (int i=1; i<=m; ++i)
    {
        int x1,x2,y1,y2;
        fin>>x1>>y1>>x2>>y2;
        query[++nr].x=x1-1;
        query[nr].y1=y1;
        query[nr].y2=y2;
        query[nr].ind=i;
        query[++nr].x=x2;
        query[nr].y1=y1;
        query[nr].y2=y2;
        query[nr].ind=-i;
    }
    sort(query+1,query+n+1,acomp2);
    int i=1,j=1;
    while (i<=n && j<=nr)
    {
        if (v[i].x <= query[j].x)
        {
            update(0,4e9,v[i].y+2e9,t);
            i++;
        }
        else
        {
            int x=cauta(0,4e9,query[j].y1+2e9,query[j].y2+2e9,t);
            if (query[j].ind>0)
            {
                ans[query[j].ind]-=x;
            }
            else
            {
                ans[-query[j].ind]+=x;
            }
            j++;
        }
    }
    while (j<=nr)
    {
        int x=cauta(0,4e9,query[j].y1+2e9,query[j].y2+2e9,t);
        if (query[j].ind>0)
        {
            ans[query[j].ind]-=x;
        }
        else
        {
            ans[-query[j].ind]+=x;
        }
        j++;
    }
    for (int i=1;i<=m;++i)
    {
        fout<<ans[i]<<"\n";
    }
    return 0;
}