Cod sursa(job #3162668)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 29 octombrie 2023 17:23:10
Problema Zoo Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <fstream>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;
ifstream fin ("zoo.in");
ofstream fout ("zoo.out");
int x1[100001],y1[100001],x2[100001],y2[100001];
int m,n,xp1,xp2,yp1,yp2,i,j,nr,sol;
vector <int> aint[64001];
pair <int,int> v[16001];
void f (int nod)
{
    int n=aint[2*nod].size ()-1;
    int m=aint[2*nod+1].size ()-1;
    int i=0,j=0;
    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=0,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=0,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].push_back (v[st].s);
    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 (v[st].f>=xp1&&v[dr].f<=xp2)
        sol+=cb2 (aint[nod],yp2)-cb1 (aint[nod],yp1)+1;
    else
    {
        if (st==dr)
            return ;
        int mij=(st+dr)/2;
        if (xp1<=v[mij].f)
            query (2*nod,st,mij);
        if (xp2>v[mij].f)
            query (2*nod+1,mij+1,dr);
    }
}
int main ()
{
    fin>>n;
    for (i=1; i<=n; i++)
        fin>>v[i].f>>v[i].s;
    sort (v+1,v+n+1);
    build (1,1,n);
    fin>>m;
    for (i=1; i<=m; i++)
        fin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
    for (i=1; i<=m; i++)
    {
        sol=0;
        xp1=x1[i];
        yp1=y1[i];
        xp2=x2[i];
        yp2=y2[i];
        query (1,1,n);
        fout<<sol<<"\n";
    }
    return 0;
}