Cod sursa(job #1537045)

Utilizator CiurezAndreiCiurez Marius-Andrei CiurezAndrei Data 26 noiembrie 2015 21:24:05
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <fstream>
#include <algorithm>
#include <vector>

#define x first
#define y second
#define DIM 16001

using namespace std;

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

int N, M, a1, a2, b1, b2, nr;
pair<int, int> v[DIM];
vector<int> A[4 * DIM];

void build(int nod, int st, int dr)
{
    if(st == dr)
    {
        A[nod].push_back(st);
        return;
    }
    else
    {
        int mid = ((st + dr) >> 1);

        build((nod << 1), st, mid);
        build((nod << 1) + 1, mid + 1, dr);

        int i = 0, j = 0;
        int left = (nod << 1), right  = (nod << 1) + 1;

        while(i < A[left].size() && j < A[right].size())
        {
            if( v[ A[left][i] ].y  < v[ A[right][j] ].y)
            {
                A[nod].push_back(  A[left][i] );
                i ++;
            }
            else
            {
                A[nod].push_back(  A[right][j] );
                j ++;
            }
        }

        for(; i < A[left].size(); i ++)
        {
            A[nod].push_back( A[left][i] );
        }
        for(; j < A[right].size(); j ++)
        {
            A[nod].push_back( A[right][j] );
        }
    }

}

void query(int nod, int st, int dr, int a1, int b1, int a2, int b2)
{
    if(a1 <= v[st].x && v[dr].x <= a2)
    {
        int p = 0, mid, pReplace, u = A[nod].size() - 1;

        while(p <= u)
        {
            mid = ((p + u) >> 1);
            if(v[ A[nod][mid] ].y < b1)
            {
                p = mid + 1;
            }
            else
            {
                u = mid - 1;
            }
        }

        pReplace = p;
        p = 0;
        u = A[nod].size() - 1;

        while(p <= u)
        {
            mid = ((p + u) >> 1);
            if(v[ A[nod][mid] ].y <= b2)
            {
                p = mid + 1;
            }
            else
            {
                u = mid - 1;
            }
        }
        nr += u - pReplace + 1;
    }
    else
    {
        int mid = ((st + dr) >> 1);
        if(v[mid].x >= a1)
        {
            query((nod << 1),st, mid, a1, b1, a2, b2);
        }
        if(v[mid + 1].x <= a2)
        {
            query((nod << 1) + 1, mid + 1, dr, a1, b1, a2, b2);
        }
    }
}

int main()
{

    fin >> N;

    for(int i = 1; i <= N; i ++)
    {
        fin >> v[i].x >> v[i].y;
    }

    sort(v + 1, v + N + 1);
    build(1, 1, N);

    fin >> M;

    while(M --)
    {
        fin >> a1 >> b1 >> a2 >> b2;
        nr = 0;

        if(v[1].x > a2 || v[N].x < a1)
        {
            fout << "0\n";
            continue;
        }

        query(1, 1, N, a1, b1, a2, b2);

        fout << nr <<'\n';
    }

    return 0;
}