Cod sursa(job #1526587)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 16 noiembrie 2015 21:36:22
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int x1,y1,x2,y2;
pair<int,int> v[16010];
vector<int> arbint[70000];
void build_arbint(int node,int left,int right){
    int middle=(left+right)/2,left_size,right_size,i,j;
    if(left==right){
        arbint[node].push_back(v[left].second);
        return;
    }
    build_arbint(2*node,left,middle);
    build_arbint(2*node+1,middle+1,right);
    left_size=arbint[2*node].size();
    right_size=arbint[2*node+1].size();
    i=j=0;
    while(i<left_size&&j<right_size)
        if(arbint[2*node][i]<arbint[2*node+1][j]){
            arbint[node].push_back(arbint[2*node][i]);
            i++;
        }
        else{
            arbint[node].push_back(arbint[2*node+1][j]);
            j++;
        }
    while(i<left_size){
        arbint[node].push_back(arbint[2*node][i]);
        i++;
    }
    while(j<right_size){
        arbint[node].push_back(arbint[2*node+1][j]);
        j++;
    }
}
int query(int node,int left,int right){
    int start,finish,middle=(left+right)/2,answer=0;
    if(x1<=v[left].first&&v[right].first<=x2){
        start=lower_bound(arbint[node].begin(),arbint[node].end(),y1)-arbint[node].begin();
        finish=upper_bound(arbint[node].begin(),arbint[node].end(),y2)-arbint[node].begin();
        return finish-start;
    }
    if(left==right)
        return 0;
    if(x1<=v[middle].first)
        answer+=query(2*node,left,middle);
    if(v[middle+1].first<=x2)
        answer+=query(2*node+1,middle+1,right);
    return answer;
}
int main(){
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    int n,x,y,i,t,q;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        v[i]=make_pair(x,y);
    }
    sort(v+1,v+n+1);
    build_arbint(1,1,n);
    scanf("%d",&t);
    for(q=1;q<=t;q++){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",query(1,1,n));
    }
    return 0;
}