Cod sursa(job #1082968)

Utilizator Ionut228Ionut Calofir Ionut228 Data 15 ianuarie 2014 14:34:53
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.23 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

struct coord
{
    int x, y;
};
coord P[16002];

int N, M;
int X1, X2, Y1, Y2;
int start, finish;
int sol;
vector<int> V[16 * 16002];

bool cmp(coord A, coord B)
{
    return (A.x < B.x || (A.x == B.x && A.y < B.y));
}

void interclasare(int nod)
{
    vector<int>::iterator f1, f2;
    f1 = V[2 * nod].begin();
    f2 = V[2 * nod + 1].begin();

    while (f1 != V[2 * nod].end() && f2 != V[2 * nod + 1].end())
    {
        while (*f1 < *f2 && f1 != V[2 * nod].end())
        {
            V[nod].push_back(*f1);
            ++f1;
        }
        while (*f2 <= *f1 && f2 != V[2 * nod + 1].end())
        {
            V[nod].push_back(*f2);
            ++f2;
        }
    }
    if (f1 == V[2 * nod].end())
    {
        while (f2 != V[2 * nod + 1].end())
        {
            V[nod].push_back(*f2);
            ++f2;
        }
    }
    else if (f2 == V[2 * nod + 1].end())
    {
        while (f1 != V[2 * nod].end())
        {
            V[nod].push_back(*f1);
            ++f1;
        }
    }
}

void update(int nod, int lt, int rt)
{
    if (lt == rt)
    {
        V[nod].push_back(P[lt].y);
        return;
    }
    int mid = (lt + rt) >> 1;
    update(2 * nod, lt, mid);
    update(2 * nod + 1, mid + 1, rt);
    interclasare(nod);
}

int cb(int nod)
{
    int lt, rt;
    int sol1, sol2;

    lt = -1;
    rt = V[nod].size();
    while (rt - lt > 1)
    {
        int mid = (lt + rt) >> 1;
        if (V[nod][mid] > Y2) rt = mid;
        else                  lt = mid;
    }
    sol1 = lt;

    lt = -1;
    rt = V[nod].size();
    while (rt - lt > 1)
    {
        int mid = (lt + rt) >> 1;
        if (V[nod][mid] < Y1) lt = mid;
        else                  rt = mid;
    }
    sol2 = rt;

    return sol1 - sol2 + 1;
}

int cb_ub()
{
    int lt = 0, rt = N + 1;
    while (rt - lt > 1)
    {
        int mid  = (lt + rt) >> 1;
        if (P[mid].x > X2) rt = mid;
        else               lt = mid;
    }
    return lt;
}

int cb_lb()
{
    int lt = 0, rt = N + 1;
    while (rt - lt > 1)
    {
        int mid = (lt + rt) >> 1;
        if (P[mid].x < X1) lt = mid;
        else               rt = mid;
    }
    return rt;
}

void question(int nod, int lt, int rt)
{
    if (start <= lt && rt <= finish)
    {
        sol += cb(nod);
        //int sol1 = lower_bound(V[nod].begin(),V[nod].end(),y1)-V[nod].begin();
        //int sol2 = upper_bound(V[nod].begin(),V[nod].end(),y2)-V[nod].begin();
        return;
    }
    int mid = (lt + rt) >> 1;
    if (start <= mid) question(2 * nod, lt, mid);
    if (mid < finish)  question(2 * nod + 1, mid + 1, rt);
}

int main()
{
    fin >> N;
    for (int i = 1; i <= N; ++i)
        fin >> P[i].x >> P[i].y;
    sort(P + 1, P + N + 1, cmp);

    update(1, 1, N);

    fin >> M;
    for (int i = 1; i <= M; ++i)
    {
        fin >> X1 >> Y1 >> X2 >> Y2;
        sol = 0;
        start = cb_lb();
        finish = cb_ub();
        question(1, 1, N);
        fout << sol << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}