Cod sursa(job #3032757)

Utilizator stefanvoicaVoica Stefan stefanvoica Data 22 martie 2023 18:03:22
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
ifstream fin ("zoo.in");
ofstream fout("zoo.out");
const int dim=1602;
int n,m=1,q,sol, nox[dim],noy[dim],px[dim],py[dim];
vector<int> pct[dim],aint[dim*4];

struct el
{
    int pct,ord;
}ox[dim],oy[dim];

inline bool cmp (const el &a1,const el &a2)
{
    return a1.pct<a2.pct;
}

inline bool aint_cmp (const int &a1,const int &a2)
{ ///sortam dupa y
    if (py[a1] == py[a2])
    return px[a1] < px[a2];
    return py[a1] < py[a2];
}

void create(int nod,int st,int dr) ///pe axa Ox
{
    if (st==dr)
    {
        for (auto y:pct[st])
        aint[nod].push_back(y);
        sort(aint[nod].begin(),aint[nod].end(),aint_cmp);
        return;
    }
    int mij=(st+dr)/2;
    create(2*nod,st,mij);
    create(2*nod+1,mij+1,dr);
    for (auto y:aint[2*nod])
        aint[nod].push_back(y);
    for (auto y:aint[2*nod+1])
        aint[nod].push_back(y);
    sort(aint[nod].begin(),aint[nod].end(),aint_cmp);
}

int cb_st (int st,int dr, int v[],int x)
{
    int sol=dr+1;
    while (st<=dr)
    {
        int mij=(st+dr)/2;
        if (v[mij] >= x)
            sol=mij, dr=mij-1;
        else    st=mij+1;
    }
    return sol;
}


int cb_dr (int st,int dr, int v[],int x)
{
    int sol=0;
    while (st<=dr)
    {
        int mij=(st+dr)/2;
        if (v[mij] <= x)
            sol=mij, st=mij+1;
        else    dr=mij-1;
    }
    return sol;
}


int aint_dr (int st,int dr, int lin,int x)
{
    int sol=-1;
    while (st<=dr)
    {
        int mij=(st+dr)/2;
        if (py[aint[lin][mij]] <= x)
            sol=mij, st=mij+1;
        else    dr=mij-1;
    }
    return sol+1;
}


int query (int nod,int st,int dr,int ql,int qr,int yl,int yr)
{
    if (qr<st || dr<ql)
        return 0;
    if (st==ql && qr==dr)
    {
        int nr=aint_dr(0,aint[nod].size()-1,nod,yr);
        if (yl>=2)
        nr=nr-aint_dr(0,aint[nod].size()-1,nod,yl-1);
        return nr;
    }
    int mij=(st+dr)/2;
    if (qr<=mij)
        return query(2*nod,st,mij,ql,qr,yl,yr);
    else if (mij+1<=ql)
        return query(2*nod+1,mij+1,dr,ql,qr,yl,yr);
    else {
        int a=query(2*nod,st,mij,ql,mij,yl,yr);
        int b=query(2*nod+1,mij+1,dr,mij+1,qr,yl,yr);
        return a+b;
    }
}

int32_t main()
{
    fin>>n;

    for (int i=1; i<=n; i++)
    {
        fin>>ox[i].pct>>oy[i].pct;
        ox[i].ord=i, oy[i].ord=i;
    }
    sort(ox+1,ox+n+1,cmp);
    sort(oy+1,oy+n+1,cmp);

    int n0=1, xi, yi, xf, yf;
    for (int i=1;i<=n;i++)
    {
        nox[n0]=ox[i].pct;
        pct[n0].push_back(ox[i].ord);
        px[ox[i].ord]=n0;

        if (i<n && ox[i].pct != ox[i+1].pct)
            n0++;
    }

    for (int i=1;i<=n;i++)
    {
        noy[m]=oy[i].pct;
        py[oy[i].ord]=m;

        if (i<n && oy[i].pct != oy[i+1].pct)
            m++;
    }

    n=n0;

    create(1,1,n);
    fin>>q;
    while (q--)
    {
        fin >> xi >> yi >> xf >> yf;
        xi=cb_st(1,n,nox,xi);
        yi=cb_st(1,m,noy,yi);
        xf=cb_dr(1,n,nox,xf);
        yf=cb_dr(1,m,noy,yf);
        fout<<query(1,1,n,xi,xf,yi,yf)<<'\n';
    }
    return 0;
}