Cod sursa(job #2413899)

Utilizator 12222Fendt 1000 Vario 12222 Data 23 aprilie 2019 19:46:11
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.68 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

const int Nmax=16005;

int n,m;

struct Punct
{
    int x,y;

    bool operator <(const Punct &e)const
    {
        return x<e.x;
    }
}aux[Nmax];

vector<int>a,aint[4*Nmax];

void Build(int nod,int st,int dr)
{
    if(st==dr)
    {
        aint[nod].push_back(aux[st].y);
        return ;
    }

    int mij=(st+dr)/2;

    Build(2*nod,st,mij);
    Build(2*nod+1,mij+1,dr);

    aint[nod].resize(aint[2*nod].size()+aint[2*nod+1].size());

    merge(aint[2*nod].begin(),aint[2*nod].end(),
          aint[2*nod+1].begin(),aint[2*nod+1].end(),
          aint[nod].begin());
}

int Query(int nod,int st,int dr,int l,int r,int y1,int y2)
{
    if(l<=st && dr<=r)
        return upper_bound(aint[nod].begin(),aint[nod].end(),y2)-lower_bound(aint[nod].begin(),aint[nod].end(),y1);

    int mij=(st+dr)/2;
    int te_sparg_frt_1=0,te_sparg_frt_2=0;

    if(l<=mij)te_sparg_frt_1=Query(2*nod,st,mij,l,r,y1,y2);
    if(mij<r)te_sparg_frt_2=Query(2*nod+1,mij+1,dr,l,r,y1,y2);

    return te_sparg_frt_1+te_sparg_frt_2;
}

int main()
{
    fin>>n;

    for(int i=1;i<=n;i++)
        fin>>aux[i].x>>aux[i].y;

    sort(aux+1,aux+n+1);

    for(int i=1;i<=n;i++)
        a.push_back(aux[i].x);

    Build(1,1,n);

    int pos1,pos2,x1,x2,y1,y2;

    fin>>m;
    while(m--)
    {
        fin>>x1>>y1>>x2>>y2;

        pos1=lower_bound(a.begin(),a.end(),x1)-a.begin();
        pos2=upper_bound(a.begin(),a.end(),x2)-a.begin()-1;

        if(pos2>=0 && pos1<n)fout<<Query(1,1,n,pos1+1,pos2+1,y1,y2)<<"\n";
        else fout<<"0\n";
    }
    return 0;
}