Cod sursa(job #1234531)

Utilizator ArchazeyBaltatu Andrei-Mircea Archazey Data 27 septembrie 2014 15:19:14
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.87 kb
#include<bits/stdc++.h>
using namespace std;

struct points
{
    int x,y;
};

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

const int NMAX=16005;

int n,m;
points a[NMAX];
vector<int>aint[4*NMAX];
vector<int>::iterator it,pit;

inline bool cmp(const points A,const points B)
{
    return A.x<B.x;
}

inline void CreateAint(int nod,int st,int dr)
{
    if (st==dr)
        {
            aint[nod].push_back(a[st].y);
            return ;
        }
    else
        {
            int mij;
            mij=(st+dr)>>1;
            CreateAint(2*nod,st,mij);
            CreateAint(2*nod+1,mij+1,dr);
            it=aint[2*nod].begin();pit=aint[2*nod+1].begin();
            while (it!=aint[2*nod].end() && pit!=aint[2*nod+1].end())
                {
                    if (*it<*pit)
                        {
                            aint[nod].push_back(*it);
                            it++;
                        }
                    else
                        {
                            aint[nod].push_back(*pit);
                            pit++;
                        }
                }
            while (it!=aint[2*nod].end())
                {
                    aint[nod].push_back(*it);
                    it++;
                }
            while (pit!=aint[2*nod+1].end())
                {
                    aint[nod].push_back(*pit);
                    pit++;
                }
        }
}

inline int QUERY(int nod,int st,int dr,int b,int c,int d,int e)
{
    if (b<=st && dr<=c)
        {
            int aux=upper_bound(aint[nod].begin(),aint[nod].end(),e)-lower_bound(aint[nod].begin(),aint[nod].end(),d);
            return aux;
        }
    else
        {
            int mij,rez=0;
            mij=(st+dr)>>1;
            if (b<=mij) rez+=QUERY(2*nod,st,mij,b,c,d,e);
            if (c>mij) rez+=QUERY(2*nod+1,mij+1,dr,b,c,d,e);
            return rez;
        }

}

int main()
{
    int i,x,y,w,z,sol1,sol2,st,dr,mij;
    fin>>n;
    for (i=1;i<=n;i++)  fin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmp);
    CreateAint(1,1,n);
    fin>>m;
    for (i=1;i<=m;i++)
        {
            fin>>x>>y>>w>>z;
            sol1=sol2=0;
            st=1;dr=n;
            while (st<=dr)
                {
                    mij=(st+dr)>>1;
                    if (a[mij].x>=x) {sol1=mij;dr=mij-1;}
                    else st=mij+1;
                }
            if (sol1==0) sol1=n+1;
            st=1;dr=n;
            while (st<=dr)
                {
                    mij=(st+dr)>>1;
                    if (a[mij].x<=w) {sol2=mij;st=mij+1;}
                    else dr=mij-1;
                }
            if (sol1<sol2 || (sol1==sol2 && a[sol1].x>=x && a[sol1].x<=w))
                fout<<QUERY(1,1,n,sol1,sol2,y,z)<<"\n";
            else fout<<"0\n";
        }
    return 0;
}