Cod sursa(job #3162658)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 29 octombrie 2023 16:51:04
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <fstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
ifstream fin ("zoo.in");
ofstream fout ("zoo.out");
int x[16001],y[16001],x1[16001],y1[16001],x2[16001],y2[16001];
int m,n,xp1,xp2,yp1,yp2,i,j,nr,sol;
vector <int> aint[928001],v,p[232001];
unordered_map <int,int> fr;
void f (int nod)
{
    aint[nod].push_back (0);
    int n=aint[2*nod].size ()-1;
    int m=aint[2*nod+1].size ()-1;
    int i=1,j=1;
    while (i<=n&&j<=m)
    {
        if (aint[2*nod][i]<=aint[2*nod+1][j])
            aint[nod].push_back (aint[2*nod][i++]);
        else
            aint[nod].push_back (aint[2*nod+1][j++]);
    }
    while (i<=n)
        aint[nod].push_back (aint[2*nod][i++]);
    while (j<=m)
        aint[nod].push_back (aint[2*nod+1][j++]);
}
int cb1 (vector <int> &v,int x)
{
    int st=1,dr=v.size ()-1,mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (v[mij]>=x)
            dr=mij-1;
        else
            st=mij+1;
    }
    return st;
}
int cb2 (vector <int> &v,int x)
{
    int st=1,dr=v.size ()-1,mij;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (v[mij]<=x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return dr;
}
void build (int nod,int st,int dr)
{
    if (st==dr)
        aint[nod]=p[st];
    else
    {
        int mij=(st+dr)/2;
        build (2*nod,st,mij);
        build (2*nod+1,mij+1,dr);
        f (nod);
    }
}
void query (int nod,int st,int dr)
{
    if (st>=xp1&&dr<=xp2)
        sol+=cb2 (aint[nod],yp2)-cb1 (aint[nod],yp1)+1;
    else
    {
        int mij=(st+dr)/2;
        if (xp1<=mij)
            query (2*nod,st,mij);
        if (xp2>mij)
            query (2*nod+1,mij+1,dr);
    }
}
int main ()
{
    fin>>n;
    for (i=1; i<=n; i++)
    {
        fin>>x[i]>>y[i];
        v.push_back (x[i]);
    }
    fin>>m;
    for (i=1; i<=m; i++)
    {
        fin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
        v.push_back (x1[i]);
        v.push_back (x2[i]);
    }
    sort (v.begin (),v.end ());
    nr=0;
    fr[v[0]]=++nr;
    for (i=1; i<v.size (); i++)
    {
        if (v[i]!=v[i-1])
            fr[v[i]]=++nr;
    }
    for (i=1; i<=nr; i++)
        p[i].push_back (0);
    for (i=1; i<=n; i++)
    {
        x[i]=fr[x[i]];
        p[x[i]].push_back (y[i]);
    }
    for (i=1; i<=m; i++)
    {
        x1[i]=fr[x1[i]];
        x2[i]=fr[x2[i]];
    }
    build (1,1,nr);
    for (i=1; i<=m; i++)
    {
        sol=0;
        xp1=x1[i];
        yp1=y1[i];
        xp2=x2[i];
        yp2=y2[i];
        query (1,1,nr);
        fout<<sol<<"\n";
    }
    return 0;
}