Cod sursa(job #341987)

Utilizator hendrikHendrik Lai hendrik Data 20 august 2009 11:30:04
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

#define MAXN 16001
#define sz size()
#define pb push_back
#define INF 2000000005

struct pii{
    int x,y;
    pii(){
    }
    bool operator <(const pii &X)const{
        return (x<X.x) || (x==X.x || y<X.y);
    }
};

int n,m,x1,y1,x2,y2,res;
pii p[MAXN];
vector<int> vtr[MAXN*4];

void inter(int node,int left,int right){
    int sl=(node<<1);
    int sr=(node<<1)|1;
    int cleft,cright;
    vtr[sl].pb(INF);
    vtr[sr].pb(INF);
    cleft=cright=0;
    for (int i=0;i<=right-left;i++){
        if (vtr[sl][cleft]<vtr[sr][cright]){
            vtr[node].pb(vtr[sl][cleft++]);
        }
        else {
            vtr[node].pb(vtr[sr][cright++]);
        }
    }
}

void build(int node,int left,int right){
    if (left==right){
        vtr[node].pb(p[left].y);
    }
    else {
        int mid=(left+right)>>1;
        build(node<<1,left,mid);
        build((node<<1)|1,mid+1,right);
        inter(node,left,right);
    }
}

int search(int node,int y1,int y2){
    if (vtr[node][0]>y2) return 0;
    if (vtr[node][vtr[node].sz-1]<y1) return 0;
    int low=lower_bound(vtr[node].begin(),vtr[node].end(),y1)-vtr[node].begin();
    int high=upper_bound(vtr[node].begin(),vtr[node].end(),y2)-vtr[node].begin();
    return high-low;
    
}

void query(int node,int left,int right){
    //cout<<node<<' '<<left<<' '<<right<<endl;
    //system("pause");
    if (x1<=p[left].x && p[right].x<=x2){
        res+=search(node,y1,y2);
    }
    else {
        int mid=(left+right)>>1;
        if (x1<=p[mid].x) query(node<<1,left,mid);
        if (x2>=p[mid+1].x) query((node<<1)|1,mid+1,right);
    }
}

void open(){
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
}

int main(){
    open();
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        scanf("%d %d",&p[i].x,&p[i].y);
    }
    sort(p+1,p+n+1);
    build(1,1,n);
    scanf("%d",&m);
    for (int i=0;i<m;i++){
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        res=0;
        query(1,1,n);
        printf("%d\n",res);
    }
    //system("pause");
    return 0;
}