Cod sursa(job #995728)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 10 septembrie 2013 10:28:29
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 16010
#define lim 1000000
#define Next (++poz == lim?(f.read(Buffer, lim), poz = 0):0)

using namespace std;

ifstream f("zoo.in");
struct Punct
{
    int x, y;
    bool operator <(const Punct &A) const
    {
        return x < A.x;
    }

};
Punct a[NMAX];
int px[NMAX];
vector <int> aint[4*NMAX];
int p, q, n, m;
int X1, X2, Y1, Y2, sol;
int poz;
char Buffer[lim];

inline void Read( int &x )
{
    int sign = 1;
    for (; Buffer[poz] < '0' || Buffer[poz] > '9' ; Next)
        if(Buffer[poz]=='-')
            sign = -1;
    for (x = 0 ; Buffer[poz] >= '0' && Buffer[poz] <= '9' ; x = x * 10 + Buffer[poz] - '0', Next) ;
    x *= sign;
}

inline void BuildTree(const int node, const int st, const int dr)
{
    if (st == dr)
    {
        aint[node].push_back(a[st].y);
        return ;
    }

    int mij = (st+dr) >> 1;
    BuildTree(node*2, st, mij);
    BuildTree(node*2+1, mij+1, dr);

    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 void Query(const int node, const int st, const int dr)
{
    if (p <= st && dr <= q)
    {
        sol += upper_bound(aint[node].begin(), aint[node].end(), Y2) - lower_bound(aint[node].begin(), aint[node].end(), Y1);
        return;
    }

    int mij = (st+dr)>>1;
    if (p <= mij)
        Query(node*2, st, mij);
    if (mij < q)
        Query(node*2+1, mij+1, dr);
}

int main()
{
    f.read(Buffer, lim);
    ofstream g ("zoo.out");
    Read(n);
    int i;
    for (i=1; i<=n; ++i)
    {
        Read(a[i].x), Read(a[i].y);
        px[i] = a[i].x;
    }
    sort(a+1, a+n+1);
    sort(px+1, px+n+1);

    BuildTree(1, 1, n);
    Read(m);
    while (m--)
    {
        Read(X1), Read(Y1), Read(X2), Read(Y2);
        if (X2 < px[1] || X1 > px[n])
            g<<"0\n";
        else
        {
            sol = 0;
            p = lower_bound(px+1, px+n+1, X1) - px;
            q = upper_bound(px+1, px+n+1, X2) - px - 1;
            Query(1, 1, n);
            g<<sol<<"\n";
        }
    }
    f.close();
    g.close();
    return 0;
}