Cod sursa(job #588968)

Utilizator tamas_iuliaTamas Iulia tamas_iulia Data 10 mai 2011 12:18:03
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include <stdio.h>
#include <algorithm>
#define Nmax 16005
#define Logmax 16
using namespace std;

struct punct {
    int x,y;
    inline bool operator < ( const punct &o ) const {
        return (x==o.x ? y<o.y : x<o.x);
    }
} P[Nmax];
int a[Logmax][Nmax];
int N,M,x1,y1,x2,y2,poz_x1,poz_x2,sol;

inline int caut_bin1(int a[], int l,int r,int val){
    int m,ret=r+1;
    while( l<= r){
        m=l+(r-l)/2;
        if( a[m] >= val ) ret=m, r=m-1;
        else l=m+1;
    }
    return ret;
}
inline int caut_bin2(int a[], int l,int r,int val){
    int m,ret=l-1;
    while( l<= r){
        m=l+(r-l)/2;
        if( a[m] <= val ) ret=m, l=m+1;
        else r=m-1;
    }
    return ret;
}
inline int caut_binx1( int l,int r,int val){
    int m,ret=r+1;
    while( l<= r){
        m=l+(r-l)/2;
        if( P[m].x >= val ) ret=m, r=m-1;
        else l=m+1;
    }
    return ret;
}
inline int caut_binx2( int l,int r,int val){
    int m,ret=l-1;
    while( l<= r){
        m=l+(r-l)/2;
        if( P[m].x <= val ) ret=m, l=m+1;
        else r=m-1;
    }
    return ret;
}

inline void Query(int l,int r,int niv){
    if( poz_x1 <= l && r<=poz_x2 ){
        int nr1,nr2;
        nr1 = caut_bin1(a[niv],l,r,y1)-1;
        nr2 = caut_bin2(a[niv],l,r,y2);
        if( nr1<=nr2 ) sol += nr2-nr1;
        return;
    }
    int m=l+(r-l)/2;
    if( poz_x1<=m ) Query(l,m,niv+1);
    if( m<poz_x2 ) Query(m+1,r,niv+1);
}

inline void Update(int l,int r,int niv){
    if( l==r ){
        a[niv][l]=P[l].y;
        return;
    }
    int m=l+(r-l)/2;
    if( l<=m ) Update(l,m,niv+1);
    if( m<r ) Update(m+1,r,niv+1);

    int i,i1,i2;
    for(i=l, i1=l, i2=m+1; i1<=m && i2<=r; ++i)
        if( a[niv+1][i1] < a[niv+1][i2] ) a[niv][i] = a[niv+1][i1++];
        else a[niv][i] = a[niv+1][i2++];
    while( i1<=m ) a[niv][i++]=a[niv+1][i1++];
    while( i2<=r ) a[niv][i++]=a[niv+1][i2++];
}

int main(){
    int i;
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
    scanf("%d",&N);
    for(i=1;i<=N;++i) scanf("%d%d",&P[i].x,&P[i].y);
    sort(P+1,P+N+1);

    Update(1,N,0);

    scanf("%d",&M);
    for(i=1;i<=M;++i){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

        poz_x1=caut_binx1(1,N,x1);
        poz_x2=caut_binx2(1,N,x2);

        sol=0;
        if( poz_x1<=poz_x2 )
            Query(1,N,0);

        printf("%d\n",sol);
    }

    fclose(stdin); fclose(stdout);
    return 0;
}