Cod sursa(job #341992)

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

#define MAXN 16005
#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;
    
}*/

int search(int node, int y1, int y2){
    int m, li, lf, cnt_y1, cnt_y2;
    if (vtr[node][0] > y2) return 0;
    if (vtr[node][vtr[node].size() - 1] < y1) return 0;
    
    li = 0, lf = vtr[node].size() - 1;
    
    while (li <= lf){
        m = (li + lf) >> 1;
        if (vtr[node][m] < y1) li = m + 1;
           else lf = m - 1;
    }
    while (vtr[node][m - 1] >= y1 && m) --m;
    while (vtr[node][m] < y1 && m < vtr[node].size() - 1) ++m;
    cnt_y1 = m;
    
    li = 0, lf = vtr[node].size() - 1;
    
    while (li <= lf){
        m = (li + lf) >> 1;
        if (vtr[node][m] < y2) li = m + 1;
           else lf = m - 1;
    }
    while (vtr[node][m + 1] <= y2 && m < vtr[node].size() - 1) ++m;
    while (vtr[node][m] > y2 && m) --m;
    cnt_y2 = m;
    
    return cnt_y2 - cnt_y1 + 1;
}

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 if (left!=right){
        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;
}