Cod sursa(job #1297692)

Utilizator acomAndrei Comaneci acom Data 22 decembrie 2014 11:33:57
Problema Zoo Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
#define NMAX 16005
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct punct
{
    int x,y;
} a[NMAX],A1,A2;
vector <int> A[NMAX<<2];
int n,m;
int cb(vector <int> &vec, punct &A, char ch);
bool cmpx(punct A, punct B)
{
    return A.x<=B.x;
}
bool cmpy(punct A, punct B)
{
    return A.y<=B.y;
}
void interclas(vector <int> &vec, vector <int> &vec1, vector <int> &vec2)
{
    vector <int>::iterator it1,it2;
    for (it1=vec1.begin(),it2=vec2.begin();it1!=vec1.end() && it2!=vec2.end();)
        if (cmpy(a[*it1],a[*it2]))
            vec.push_back(*it1), ++it1;
        else
            vec.push_back(*it2), ++it2;
    for (;it1!=vec1.end();++it1)
        vec.push_back(*it1);
    for (;it2!=vec2.end();++it2)
        vec.push_back(*it2);
}
void proc(int nod, int st, int dr)
{
    if (st==dr)
    {
        A[nod].push_back(st);
        return ;
    }
    int mij=(st+dr)>>1;
    proc(nod<<1,st,mij);
    proc(1+(nod<<1),mij+1,dr);
    interclas(A[nod],A[nod<<1],A[1+(nod<<1)]);
}
int query(int nod, int st, int dr, punct &unu, punct &doi)
{
    if (cmpx(unu,a[st]) && cmpx(a[dr],doi))
    {
        int p1=cb(A[nod],unu,'<'),p2=cb(A[nod],doi,'>');
        return p2-p1+1;
    }
    int mij=(st+dr)>>1,q1=0,q2=0;
    if (cmpx(unu,a[mij]))
        q1=query(nod<<1,st,mij,unu,doi);
    if (cmpx(a[mij+1],doi))
        q2=query(1+(nod<<1),mij+1,dr,unu,doi);
    return q1+q2;
}
int cb(vector <int> &vec, punct &A, char ch)
{
    int st=1,dr=vec.size(),mij;
    if (ch=='<')
    {
        while (st<=dr)
        {
            mij=(st+dr)>>1;
            if (cmpy(A,a[vec[mij-1]]))
                dr=mij-1;
            else
                st=mij+1;
        }
        return st;
    }
    else
    {
        while (st<=dr)
        {
            mij=(st+dr)>>1;
            if (cmpy(a[vec[mij-1]],A))
                st=mij+1;
            else
                dr=mij-1;
        }
        return dr;
    }
}
int main()
{
    int i;
    fin>>n;
    for (i=1;i<=n;++i)
        fin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,cmpx);
    proc(1,1,n);
    fin>>m;
    for (i=1;i<=m;++i)
    {
        fin>>A1.x>>A1.y>>A2.x>>A2.y;
        fout<<query(1,1,n,A1,A2)<<"\n";
    }
    return 0;
}