Cod sursa(job #828371)

Utilizator UnforgivenMihai Catalin Botezatu Unforgiven Data 3 decembrie 2012 17:59:02
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.14 kb
#include <fstream>
#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];


void quick_sort(int low, int high)
{
      if(high - low < 1)
         return;

      int left = low;
      int right = high;
      int pivot = vect[low + (high - low) / 2].x;

      while(left <= right)
      {
         while(vect[left].x < pivot)
            left++;


         while(vect[right].x > pivot)
            right--;


         if(left <= right)
         {  punct temp = vect[left];
            vect[left] = vect[right];
            vect[right] = temp;
            left++;
            right--;
         }

      }
      quick_sort( low, right);
      quick_sort( left, high);
}


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 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
        {
            left = 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(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++;
    }*/
    tree[nod].resize(tree[nod<<1].size() + tree[ (nod<<1)+1].size());
    merge(tree[nod<<1].begin(), tree[nod<<1].end(), tree[(nod<<1)+1].begin(), tree[(nod<<1)+1].end(), tree[nod].begin());
}

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);

    }
    quick_sort(1,N);
    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;
}