Cod sursa(job #995721)

Utilizator romircea2010FMI Trifan Mircea Mihai romircea2010 Data 10 septembrie 2013 10:12:03
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define NMAX 16010

using namespace std;

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;

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()
{
    ifstream f ("zoo.in");
    ofstream g ("zoo.out");
    f>>n;
    int i;
    for (i=1; i<=n; ++i)
    {
        f>>a[i].x>>a[i].y;
        px[i] = a[i].x;
    }
    sort(a+1, a+n+1);
    sort(px+1, px+n+1);

    BuildTree(1, 1, n);
    f>>m;
    while (m--)
    {
        f>>X1>>Y1>>X2>>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;
}