Cod sursa(job #857065)

Utilizator StefanLacheStefan Lache StefanLache Data 17 ianuarie 2013 11:12:58
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;

const int N=16003;

pair<int,int> coord[N];
vector <int> arbore[N*10], abscise;

ifstream fin("zoo.in");
ofstream fout("zoo.out");
int n,m;

void construieste(int nod, int st, int dr){
    if (dr == st){
        arbore[nod].push_back (coord[st].second);
        return;
    }
    int mij = (st + dr) / 2;            //mijlocul intervalului
    int l = nod * 2, r = l + 1;
    construieste (l, st, mij);                //construiesc subarborele stang
    construieste (r, mij + 1,dr); // construiesc subarborele drept
    arbore[nod].resize (dr - st + 1);
    merge(arbore[l].begin(), arbore[l].end(), arbore[r].begin(), arbore[r].end(), arbore[nod].begin());
}

int cautBinar(int nod,int y1,int y2){
    return (int)(upper_bound(arbore[nod].begin(),arbore[nod].end(),y2) - lower_bound(arbore[nod].begin(),arbore[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 mij = (x1 + x2) / 2;
    if (x < x1) return 0;
    if (x2 <= x) return cautBinar (nod, y1, y2);
    return query(2 * nod, x, x1, mij, y1, y2) + query(2 * nod + 1, x, mij + 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());
    construieste (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;
}