Cod sursa(job #1304437)

Utilizator acomAndrei Comaneci acom Data 28 decembrie 2014 22:04:42
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
#define NMAX 16005
#define LMAX 30000005
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct punct
{
    int x,y;
} a[NMAX],A1,A2;
vector <punct> A[NMAX<<2];
int n,m;
char *p,str[LMAX];
void read();
int cb(vector <punct> &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 <punct> &vec, vector <punct> &vec1, vector <punct> &vec2)
{
    vector <punct>::iterator it1,it2;
    for (it1=vec1.begin(),it2=vec2.begin();it1!=vec1.end() && it2!=vec2.end();)
        if (cmpy(*it1,*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(a[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) || st==dr)
    {
        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 <punct> &vec, punct A, char ch)
{
    int st=1,dr=vec.size(),mij;
    if (ch=='<')
    {
        while (st<=dr)
        {
            mij=(st+dr)>>1;
            if (cmpy(A,vec[mij-1]))
                dr=mij-1;
            else
                st=mij+1;
        }
        return st;
    }
    else
    {
        while (st<=dr)
        {
            mij=(st+dr)>>1;
            if (cmpy(vec[mij-1],A))
                st=mij+1;
            else
                dr=mij-1;
        }
        return dr;
    }
}
void read(int &x)
{
    int sgn=1;
    while ( !('0'<=*p && *p<='9') && *p!='-' ) ++p;
    if (*p=='-') sgn=-1, ++p;
    for (x=0;'0'<=*p && *p<='9';++p)
        x=x*10+*p-'0';
    x*=sgn;
}
int main()
{
    fin.read(str,LMAX);
    p=str;
    read(n);
    for (int i=1;i<=n;++i)
    {
        read(a[i].x);
        read(a[i].y);
    }
    sort(a+1,a+n+1,cmpx);
    proc(1,1,n);
    read(m);
    for (int i=1;i<=m;++i)
    {
        read(A1.x); read(A1.y);
        read(A2.x); read(A2.y);
        fout<<query(1,1,n,A1,A2)<<"\n";
    }
    return 0;
}