Cod sursa(job #856239)

Utilizator Marius_mFMI-M2 Marius Melemciuc Marius_m Data 16 ianuarie 2013 04:46:14
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.66 kb
/*
 * =====================================================================================
 *
 *       Filename:  zoo.cpp
 *
 *    Description:  https://infoarena.ro/problema/zoo
 *
 *        Version:  1.0
 *        Created:  01/16/2013 03:58:03 AM
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */

#include<fstream>
#include<algorithm>
#include<vector>

using namespace std;

ifstream in("zoo.in"); 
ofstream out("zoo.out");
 
int N, M;

typedef struct coordinates { int x,y; }COORDINATES;

vector<COORDINATES> animale;
vector<int> arb[2*16000 + 1000], animalex;

bool cmp(const COORDINATES& a, const COORDINATES& b)
{
	if(a.x < b.x)
		return 1;
	else
		if(a.x == b.x)
			if(a.y < b.y)
				return 1;
			else
				return 0;
		else
			return 0;
}

void update(int nod, int st, int dr){
    if(st == dr)
	{
        arb[nod].push_back(animale[st - 1].y);
        return;
    }
     
    int m = (st + dr) / 2;
    
    update(nod * 2, st, m);
    update(nod * 2 + 1, m + 1, dr);
    
    arb[nod].resize(dr - st + 1);
    merge(arb[nod*2].begin(), arb[nod * 2].end(), arb[nod*2 + 1].begin(), arb[nod*2 + 1].end(), arb[nod].begin());
}
 
int cautaBinar(vector<int> &v, int y1, int y2)
{
    int st = (int)(lower_bound(v.begin(), v.end(), y1) - v.begin());
    int dr = (int)(upper_bound(v.begin(), v.end(), y2) - v.begin());
    return dr - st;
}
 
int query(int nod, int st, int dr, int& left, int& right, int& y1, int& y2)
{
    if(right == 0 || left == N + 1)
        return 0;
     
    if (left <= st && dr <= right)
        return cautaBinar(arb[nod], y1, y2);
    
    int mij = (st + dr) / 2, result = 0;
    
    if (left <= mij) 
    	result += query(nod * 2, st, mij, left, right, y1, y2);
    if (mij < right)
        result += query(nod * 2 + 1, mij + 1, dr, left, right, y1, y2);
     
    return result;
}
 
int main()
{
    int x1, x2, y1, y2, x1_index, x2_index;
    COORDINATES z;
    
    in >> N;
 	    
    for(int i = 0 ; i < N ; i++)
    {
        in >> z.x >> z.y;
        animale.push_back(z);
        animalex.push_back(z.x);
    }
    
    sort(animale.begin(), animale.end(),cmp);
    sort(animalex.begin(), animalex.end());
     
    update(1, 1, N);
    in >> M;
     
    for(int i = 0 ; i < M ; i++)
    {
        in >> x1 >> y1 >> x2 >> y2;
         
        int x1_index = lower_bound(animalex.begin(), animalex.end(), x1) - animalex.begin() + 1;
        int x2_index = upper_bound(animalex.begin(), animalex.end(), x2) - animalex.begin();
         
        out << query(1, 1, N, x1_index, x2_index, y1, y2) << "\n";
    }
    return 0;
}