Cod sursa(job #739867)

Utilizator mihai995mihai995 mihai995 Data 23 aprilie 2012 23:40:44
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

const int N=16005;
int LG[N], X[N], Y[N], n, rez;

vector<int> aint[7*N];

ifstream in("zoo.in");
ofstream out("zoo.out");

struct Point
{
    int x,y;

    void get()
    {
        in >> x >> y;
        X[++X[0]]=x;
        Y[++Y[0]]=y;
    }

    bool operator<(const Point& P) const
    {
        return y < P.y;
    }
}punct[N];

void normalise(int v[])
{
    sort(v + 1 , v + n + 1);

    v[0]=1;
    for (int i = 2 ; i <= n ; i++)
        if (v[i] != v[i-1])
            v[++v[0]] = v[i];
}

void update(int x,int val)
{
    int poz = 1, st = 1, dr = n, m;

    while (st != dr)
    {
        aint[poz].push_back(val);
        m = (st + dr) >> 1;

        if (x <= m)
        {
            poz <<= 1;
            dr = m;
        }
        else
        {
            poz = (poz << 1) + 1;
            st = m + 1;
        }
    }

    aint[poz].push_back(val);
}

int find(vector<int>& v,int x)
{
    int i, step = LG[v.size()];
    for (i=-1 ; step ; step >>= 1)
        if (i+step < v.size() && v[i+step] <= x)
            i += step;
    return i;
}

int find(int v[],int x)
{
    int i, step = LG[ v[0] ];
    for (i=0 ; step ; step >>= 1)
        if (i + step <= v[0] && v[i + step] <= x)
            i += step;
    return i;
}

void query (int poz, int st, int dr, int x, int y,int lst, int ldr)
{
    if (x <= st && dr <= y)
    {
        rez += find(aint[poz], ldr) - find (aint[poz], lst - 1);
        return ;
    }

    int m = (st + dr) >> 1, S = poz << 1, D = S + 1;

    if (x<=m)
        query (S, st, m, x, y, lst, ldr);
    if (m<y)
        query (D, m+1, dr, x, y, lst, ldr);
}

int query (int x,int y ,int z,int t)
{
    rez=0;
    query (1, 1, n, x, y, z, t);
    return rez;
}

void compute()
{
    for (int i = 0 ; i < 14 ; i++)
        LG[1 << i] = 1 << i;
    for (int i = 1 ; i <=n ; i++)
        if (!LG[i])
            LG[i] = LG[i-1];
    normalise(X);
    normalise(Y);

    for (int i = 1 ; i <= n ; i++)
    {
        punct[i].x = find(X, punct[i].x);
        punct[i].y = find(X, punct[i].y);
    }

    sort (punct + 1, punct + n + 1);

    for (int i = 1 ; i <= n ; i++)
        update(punct[i].x, punct[i].y);
}

int main()
{
    int m, x, y, z, t;

    in>>n;

    for (int i = 1 ; i <= n ; i++)
        punct[i].get();

    compute();

    in>>m;

    while (m--)
    {
        in>>x>>y>>z>>t;
        x = find(X, x);
        y = find(Y, y);
        z = find(X, z);
        t = find(Y, t);
        out << query(x,z,y,t) << "\n";
    }
    return 0;
}