Cod sursa(job #833798)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 13 decembrie 2012 03:52:12
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.84 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[160000], Px;

void Update(int nod, int st, int dr, int poz, int val){
    if (st == dr) {
        arb[nod].push_back(val);
        return;
    }
    int m = (st + dr) / 2;
    if (poz <= m) Update(2*nod, st, m, poz, val);
        else Update(2*nod + 1, m + 1, dr, poz, val);
	
	arb[nod].resize(arb[2*nod].size() + arb[2*nod + 1].size());
    merge(arb[2*nod].begin(), arb[2*nod].end(), arb[2*nod+1].begin(), arb[2*nod+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());
	
	for(i = 0; i < N; i++)
		Update(1, 1, N, i + 1, P[i].second);
	
	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";
	}
}