Cod sursa(job #843101)

Utilizator stoicatheoFlirk Navok stoicatheo Data 27 decembrie 2012 13:40:44
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.68 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;
    int l=nod<<1,r=(nod<<1)+1;
    buildTree(left,mid,l);
    buildTree(mid+1,right,r);
    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)>>1;
    if(x<left || 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;
}