Cod sursa(job #829571)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 5 decembrie 2012 16:50:41
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

ifstream in("zoo.in");
ofstream out("zoo.out");

const int N=16100;

pair<int,int> v[N];
vector <int> arb[N*10];

int n,m;

void buildTree(int left,int right,int nod){
    if(left==right){
        arb[nod].push_back(v[left].second);
		return;
    }
    int mid=(left+right)/2;
    buildTree(left,mid,2*nod);
    buildTree(mid+1,right,2*nod+1);
    int i=0,j=0;
    int l=2*nod,r=2*nod+1;
	arb[nod].reserve(right-left+1);
    while(i<arb[l].size() && j<arb[r].size()){
        if(arb[l][i]<arb[r][j]){
            arb[nod].push_back(arb[l][i]);
            ++i;
            continue;
        }
        arb[nod].push_back(arb[r][j]);
        ++j;
    }
    while(i<arb[l].size()){
        arb[nod].push_back(arb[l][i]);
        ++i;
    }
    while(j<arb[r].size()){
        arb[nod].push_back(arb[r][j]);
        ++j;
    }
}

int cautBinar(int nod,int y1,int y2){
    int st=(int)(lower_bound(arb[nod].begin(),arb[nod].end(),y1)-arb[nod].begin());
    int dr=(int)(upper_bound(arb[nod].begin(),arb[nod].end(),y2)-arb[nod].begin());
    return dr-st;
}

int query(int left,int right,int x,int nod,int y1,int y2){
    int mid=(left+right)/2;
	if(x<left){
		return 0;
	}
    if(left>x){
        return 0;
    }
    if(right<=x){
        return cautBinar(nod,y1,y2);
    }
    return query(left,mid,x,2*nod,y1,y2) + query(mid+1,right,x,2*nod+1,y1,y2);
}

void solve(){
    in>>n;
    int i,x,y;
	vector <int> vx;
    for(i=1;i<=n;++i){
        in>>x>>y;
        v[i]=make_pair(x,y);
		vx.push_back(x);
    }
    sort(v+1,v+n+1);
	sort(vx.begin(),vx.end());
    buildTree(1,n,1);
    in>>m;
    int nx1,nx2,x1,x2,y1,y2;
    for(i=1;i<=m;++i){
        in>>x1>>y1>>x2>>y2;
        nx1=upper_bound(vx.begin(),vx.end(),x1-1)-vx.begin();
        nx2=upper_bound(vx.begin(),vx.end(),x2)-vx.begin();
		out<<query(1,n,nx2,1,y1,y2)-query(1,n,nx1,1,y1,y2)<<"\n";
    }
}

int main(){
    solve();
    return 0;
}