Cod sursa(job #829544)

Utilizator vlad.doruIon Vlad-Doru vlad.doru Data 5 decembrie 2012 16:28:07
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2 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;
    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(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);
    }
    sort(v+1,v+n+1);
    buildTree(1,n,1);
    in>>m;
    int nx1,nx2,x1,x2,y1,y2;
	/*for(i=1;i<=n;++i){
		out<<v[i].first<<" ";
	}
	out<<"\n";*/
    for(i=1;i<=m;++i){
        in>>x1>>y1>>x2>>y2;
        nx1=lower_bound(v+1,v+n+1,make_pair(x1,0))-v-1;
        nx2=upper_bound(v+1,v+n+1,make_pair(x2,0))-v;
        //out<<nx1<<" "<<nx2<<"\n";
        out<<query(1,n,nx2,1,y1,y2)-query(1,n,nx1,1,y1,y2)<<"\n";
    }
}

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