Cod sursa(job #829991)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 6 decembrie 2012 09:49:01
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 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],vx;

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].resize(right-left+1);
	merge(arb[l].begin(),arb[l].end(),arb[r].begin(),arb[r].end(),arb[nod].begin());
}

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;
    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;
}