Cod sursa(job #1310911)

Utilizator acomAndrei Comaneci acom Data 7 ianuarie 2015 14:24:35
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.53 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];
int cb(vector <punct> &vec, punct A, char ch);
bool cmpx(const punct &A, const punct &B)
{
    return A.x<=B.x;
}
void proc(int nod, int st, int dr)
{
    if (st==dr)
    {
        A[nod].push_back(a[st]);
        return ;
    }
    vector <punct>::iterator it1,it2;
    int mij=(st+dr)>>1;
    proc(nod<<1,st,mij);
    proc(1+(nod<<1),mij+1,dr);
    for (it1=A[nod<<1].begin(),it2=A[1+(nod<<1)].begin();it1!=A[nod<<1].end() && it2!=A[1+(nod<<1)].end();)
        if (it1->y <= it2->y)
            A[nod].push_back(*it1), ++it1;
        else
            A[nod].push_back(*it2), ++it2;
    for (;it1!=A[nod<<1].end();++it1)
        A[nod].push_back(*it1);
    for (;it2!=A[1+(nod<<1)].end();++it2)
        A[nod].push_back(*it2);
}
int query(int nod, int st, int dr, punct unu, punct doi)
{
    if ((unu.x<=a[st].x && a[dr].x<=doi.x) || 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 (unu.x<=a[mij].x)
        q1=query(nod<<1,st,mij,unu,doi);
    if (a[mij+1].x<=doi.x)
        q2=query(1+(nod<<1),mij+1,dr,unu,doi);
    return q1+q2;
}
inline 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 (A.y<=vec[mij-1].y)
                dr=mij-1;
            else
                st=mij+1;
        }
        return st;
    }
    else
    {
        while (st<=dr)
        {
            mij=(st+dr)>>1;
            if (vec[mij-1].y<=A.y)
                st=mij+1;
            else
                dr=mij-1;
        }
        return dr;
    }
}
inline 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;
}