Cod sursa(job #995628)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 9 septembrie 2013 22:59:19
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.46 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define In "zoo.in"
#define Out "zoo.out"
#define Nmax 16005
#define Lg 100000
#define verf ++poz == Lg ? f.read (Buffer, Lg), poz = 0 : 0

using namespace std;

struct point
{
    int x, y;
    bool operator <(const point &A)const
    {
        return x < A.x;
    }
};

ifstream f(In);
char Buffer[Lg];
point v[Nmax];
int a[Nmax],ymin, ymax, n,poz;
inline void Read( int &x )
{
    int sign = 1;
    for (; Buffer[poz] < '0' || Buffer[poz] > '9' ; verf)
        if(Buffer[poz]=='-')
            sign = -1;
    for (x = 0 ; Buffer[poz] >= '0' && Buffer[poz] <= '9' ; x = x * 10 + Buffer[poz] - '0', verf) ;
    x *= sign;
}
class SegmentTree
{
    public:
    inline void Build(const int node,const int Left,const int Right)
    {
        if(Left==Right)
        {
            Aint[node].push_back(v[Left].y);
            return ;
        }
        int middle = ( Left + Right ) >> 1;
        Build(2*node,Left,middle);
        Build(2*node+1,middle+1,Right);
        Aint[node].resize(Aint[2*node].size()+Aint[2*node+1].size());
        merge(Aint[2*node].begin(),Aint[2*node].end(),Aint[2*node+1].begin(),Aint[2*node+1].end(),Aint[node].begin());
    }
    inline int Query(const int node,const int Left,const int Right,const int x,const int y)
    {
        if(x <= Left && Right <= y)
            return upper_bound(Aint[node].begin(),Aint[node].end(),ymax)-lower_bound(Aint[node].begin(),Aint[node].end(),ymin);
        int middle = ( Left + Right ) >> 1, sol1 = 0, sol2 = 0;
        if(x<=middle)
            sol1 = Query(2*node,Left,middle,x,y);
        if(middle < y)
            sol2 = Query(2*node+1,middle+1,Right,x,y);
        return sol1+sol2;
    }
    private:
    vector< int > Aint[4*Nmax];
};
SegmentTree AINT;
int main()
{
    int i, m, x, xx, ind1, ind2;
    freopen(Out,"w",stdout);
    f.read (Buffer, Lg);
    Read(n);
    for(i = 1;i <= n; ++i)
        Read(v[i].x),Read(v[i].y);
    sort(v+1,v+n+1);
    vector< int >a;
    for(i = 1;i <= n; ++i)
        a.push_back(v[i].x);
    AINT.Build(1,1,n);
    Read(m);
    for(i = 1;i <= m; ++i)
    {
        Read(x),Read(ymin),Read(xx),Read(ymax);
        ind1 = lower_bound(a.begin(),a.end(),x)-a.begin();
        ind2 = upper_bound(a.begin(),a.end(),xx)-a.begin()-1;
        if(ind1<n && ind2 >= 0)
        {
            if(a[ind2]>xx)
                --ind2;
           printf("%d\n",AINT.Query(1,1,n,ind1+1,ind2+1));
        }
        else
            printf("0\n");
    }
    return 0;
}