Cod sursa(job #850391)

Utilizator mr.johnFMI - Laceanu Ionut-Adrian mr.john Data 8 ianuarie 2013 14:40:25
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 kb
#include <fstream>
#include <algorithm>
#include <vector>  
using namespace std;
  
const int N=16003;
  
pair<int,int> coord[N];
vector <int> tree[N*10], abscise;
  
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int n,m;
  
void buildTree(int nod, int left, int right){
    if (left == right){
        tree[nod].push_back (coord[left].second);
        return;
    }
    int mid = (left + right) / 2; //mijlocul intervalului
    int l = nod * 2, r = l + 1;
    buildTree (l, left, mid); //fiul stang
    buildTree (r, mid + 1, right); // fiul drept
    tree[nod].resize (right - left + 1);
		//concatenez in nodul curent informatia din nodurile fiu
    merge(tree[l].begin(), tree[l].end(), tree[r].begin(), tree[r].end(), tree[nod].begin());
}
  
int cautBinar(int nod,int y1,int y2){
    return (int)(upper_bound(tree[nod].begin(),tree[nod].end(),y2) - lower_bound(tree[nod].begin(),tree[nod].end(),y1) );
}
  
int query(int nod, int x, int x1, int x2, int y1, int y2){
	//returnez cate puncte sunt <= x pe intervalul [y1, y2]
    int mid = (x1 + x2) / 2;
    if (x < x1) return 0;
    if (x2 <= x) return cautBinar (nod, y1, y2);
    return query(2 * nod, x, x1, mid, y1, y2) + query(2 * nod + 1, x, mid + 1, x2, y1, y2);
}

int main(){
    fin >> n;
    for(int i = 1; i <= n; ++i){
        fin >> coord[i].first >> coord[i].second;;
        abscise.push_back (coord[i].first);
    }
    sort (coord + 1, coord + n + 1);
    sort (abscise.begin(), abscise.end());
    buildTree (1, 1, n);
    fin >> m;
    int lim_x1, lim_x2, x1, x2, y1, y2;
    for(int i = 1; i <= m; ++i){
        fin >> x1 >> y1 >> x2 >> y2;
        lim_x1 = upper_bound (abscise.begin(), abscise.end(), x1 - 1) - abscise.begin();   //prima aparitie a primului numar >= x1
        lim_x2 = upper_bound (abscise.begin(), abscise.end(), x2) - abscise.begin();		//prima aparitie a primului numar > x2
        fout << query (1, lim_x2, 1, n, y1, y2) - query (1, lim_x1, 1, n, y1, y2) << "\n";
    }
    return 0;
}