Cod sursa(job #833799)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 13 decembrie 2012 04:02:31
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fin("zoo.in"); ofstream fout("zoo.out");

int N, M;
vector< pair<int, int> > P;
vector<int> arb[33000], Px;

void Update(int nod, int st, int dr){
    if(st == dr){
        arb[nod].push_back(P[st - 1].second);
        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 CautaBin(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 CautaBin(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 i, x, y, x1, x2, y1, y2;
	fin >> N;
	
	for(i = 0; i < N; i++){
		fin >> x >> y;
		P.push_back(make_pair(x, y));
		Px.push_back(x);
	}
	sort(P.begin(), P.end());
	sort(Px.begin(), Px.end());
	
	Update(1, 1, N);
	fin >> M;
	
	for (i = 0; i < M; i++){
		fin >> x1 >> y1 >> x2 >> y2;
		
		int x1_ind = lower_bound(Px.begin(), Px.end(), x1) - Px.begin() + 1;
		int x2_ind = upper_bound(Px.begin(), Px.end(), x2) - Px.begin();
		
		fout << Query(1, 1, N, x1_ind, x2_ind, y1, y2) << "\n";
	}
}