Cod sursa(job #828359)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 3 decembrie 2012 17:30:55
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.17 kb
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
#define MAX_SIZE 16000
#include <string.h>

using namespace std;



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

vector <int> tree[1 << 15];
punct vect[MAX_SIZE+1];
int N;
int y1 , y2;
char buffer[56];



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
        {
            left = middle+1;
        }
    }
    return poz;
}

int tree_search_left(int nod , int value)
{
    int size = tree[nod].size();

    if(tree[nod][size-1] < value)
    {
        return -1;
    }
    return (lower_bound(tree[nod].begin(), tree[nod].end(),value) - tree[nod].begin());
}

int tree_search_right(int nod , int value)
{
    int size = tree[nod].size();

    if(tree[nod][0] > value)
    {
        return -1;
    }

    return (lower_bound(tree[nod].begin(),tree[nod].end(),value+1) - tree[nod].begin() - 1);
}

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(2*nod,left,middle);
    build_tree(2*nod+1,middle+1,right);

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

int 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)
        return poz2 - poz1 + 1;
        else return 0;
    }
    int middle = (left + right) >> 1;
    int r1= 0,r2 = 0;
    if (middle >= A) r1 = query_tree(2*nod,left,middle,A,B);
    if (B> middle)  r2 = query_tree(2*nod+1,middle+1,right,A,B);
    return r1+r2;
}

int convert_to_number(int &poz)
{
    int semn = 1;

    if (buffer[poz] == '-')
    {
        semn *= -1;
        poz++;
    }
    int number = 0;
    while ( poz < strlen(buffer) && buffer[poz] != ' ')
    {
        number = number * 10 + (buffer[poz] - '0');
        poz++;
    }
    poz++;
    return semn * number;
}

int main()
{
    ifstream input("zoo.in");
    ofstream output("zoo.out");
    int pos = 0;
    input.getline(buffer,56);
    N = convert_to_number(pos);
    for (int i = 1;i<=N;i++)
    {
        pos = 0;
        input.getline(buffer,56);
        vect[i].x = convert_to_number(pos);
        vect[i].y = convert_to_number(pos);

    }
    sort(vect+1 , vect + N + 1 , cmp);
    build_tree(1,1,N);
    pos = 0;
    input.getline(buffer,56);
    int M = convert_to_number(pos);


    for (int i = 0 ; i < M;i++)
    {
        pos = 0;
        input.getline(buffer,56);
        int x1 = convert_to_number(pos);
        y1 = convert_to_number(pos);
        int x2 = convert_to_number(pos);
        y2 = convert_to_number(pos);
        int poz1 = vect_search_left(x1);
        int poz2 = vect_search_right(x2);
        int answer = 0;
        if (poz1 != -1 && poz2 != -1)
        {
            answer = query_tree(1,1,N,poz1,poz2);

        }
        output << answer << "\n";
    }
    input.close();
    output.close();


    return 0;
}