Cod sursa(job #828261)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 3 decembrie 2012 15:47:26
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.94 kb
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define left_son ((nod)<<1)
#define right_son ((nod)<<1)+1
#define MAX_SIZE 16000

using namespace std;



typedef struct
{
    int x;
    int y;
}punct;

vector <int> tree[3*MAX_SIZE];
punct vect[MAX_SIZE+1];
int N;
int y1 , y2;
int answer;

bool cmp(punct a1 , punct a2)
{
    return (a1.x < a2.x);
}

int vect_search_right(int value)
{
    int left = 1;
    int right = N;
    int poz = -1;
    while (left <= right)
    {
        int middle = (left + right) >> 1;
        if (vect[middle].x <= value)
        {
            left = middle+1;
            poz = middle;
        }
        else
        {
            right = middle-1;
        }
    }
    return poz;
}

int vect_search_left(int value)
{
    int left = 1;
    int right = N;
    int poz = -1;
    while (left <= right)
    {
        int middle = (left + right) >> 1;
        if (vect[middle].x >= value)
        {
            right = middle-1;
            poz = middle;
        }
        else
        {
            right = middle-1;
        }
    }
    return poz;
}

int tree_search_left(int nod , int value)
{
    int left = 0;
    int right = tree[nod].size()-1;
    int poz = -1;
    while (left <= right)
    {
        int middle = (left + right) >> 1;
        if (tree[nod][middle] >= value)
        {
            right = middle-1;
            poz = middle;
        }
        else
        {
            right = middle-1;
        }
    }
    return poz;
}

int tree_search_right(int nod , int value)
{
    int left = 0;
    int right = tree[nod].size()-1;
    int poz = -1;
    while (left <= right)
    {
        int middle = (left + right) >> 1;
        if (tree[nod][middle] <= value)
        {
            left = middle+1;
            poz = middle;
        }
        else
        {
            right = middle-1;
        }
    }
    return poz;
}

void build_tree(int nod , int left , int right)
{
    if (left == right)
    {
        tree[nod].push_back(vect[left].y);
        return;
    }
    int middle = (left + right) >> 1;
    build_tree(left_son,left,middle);
    build_tree(right_son,middle+1,right);

    int size1 = tree[left_son].size();
    int size2 = tree[right_son].size();
    int k1 = 0;
    int k2 = 0;
    while (k1 < size1 && k2 < size2)
    {
        if (tree[left_son][k1] < tree[right_son][k2])
        {
            tree[nod].push_back(tree[left_son][k1]);
            k1++;
        }
        else
        {
            tree[nod].push_back(tree[right_son][k2]);
            k2++;
        }
    }
    while (k1 < size1)
    {
        tree[nod].push_back(tree[left_son][k1]);
        k1++;
    }
    while (k2 < size2)
    {
        tree[nod].push_back(tree[right_son][k2]);
        k2++;
    }
}

void query_tree(int nod , int left , int right , int A , int B)
{
    if ( A <= left && right <= B)
    {
        int poz1 = tree_search_left(nod,y1);
        int poz2 = tree_search_right(nod,y2);
        if (poz1 != -1 && poz2 != -1)
        answer += poz2 - poz1 + 1;
        return;
    }
    int middle = (left + right) >> 1;

    if (middle >= A) query_tree(left_son,left,middle,A,B);
    if (B> middle)  query_tree(right_son,middle+1,right,A,B);

}

int main()
{
    ifstream input("zoo.in");
    ofstream output("zoo.out");
    input >> N;
    for (int i = 1;i<=N;i++)
    {
        input >> vect[i].x >> vect[i].y;

    }
    sort(vect+1 , vect + N + 1 , cmp);
    build_tree(1,1,N);
    int M;
    input >> M;
    for (int i = 0 ; i < M;i++)
    {
        punct a1;
        punct a2;
        input >> a1.x >> a1.y >> a2.x >> a2.y;
        int poz1 = vect_search_left(a1.x);
        int poz2 = vect_search_right(a2.x);
        y1 = a1.y;
        y2 = a2.y;
        answer = 0;
        if (poz1 != -1 && poz2 != -1)
        {
            query_tree(1,1,N,poz1,poz2);
            output << answer << "\n";
        }
        else
        {
            output << 0;
        }
    }
    input.close();
    output.close();
    return 0;
}