Cod sursa(job #1386173)

Utilizator bogdanpaunFMI Paun Bogdan Gabriel bogdanpaun Data 12 martie 2015 19:22:35
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <utility>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

#define N 16500
int n ,  m, i   ;
pair<int,int> a[N];
vector<int> x , arb[4*N] ;

void build(int nod,int st,int dr){
    if( st == dr ){
        arb[nod].assign(1, a[st].second );
        return;
    }
    int mid = (st+dr) >> 1;
    build( nod<<1    , st , mid );
    build( (nod<<1)+1, mid+1,  dr );
    arb[nod].resize( arb[nod<<1].size() + arb[nod*2+1].size()  );
    merge( arb[nod<<1].begin() , arb[nod<<1].end(), arb[nod*2+1].begin() , arb[nod*2+1].end() , arb[nod].begin() );
}

int query(int nod,int st,int dr,int x1,int x2,int y1,int y2){
    if( x1 <= st && dr <= x2 )
        return upper_bound( arb[nod].begin() , arb[nod].end() , y2 )
             - lower_bound( arb[nod].begin() , arb[nod].end() , y1 );
    if( st == dr ) return 0;
    int mid = (st+dr)>>1 , sol =0;
    if( x1 <= mid )
        sol = query( nod*2  , st  , mid,x1,x2,y1,y2 );
    if( x2  > mid )
        sol+= query( nod*2+1,mid+1,dr,x1,x2,y1,y2   );
    return sol;
}


int main()
{
    freopen("zoo.in" ,"r",stdin);
    freopen("zoo.out","w",stdout);

    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%d %d",&a[i].first,&a[i].second);
        x.push_back( a[i].first );
    }
    sort( x.begin() , x.end()  );
    sort( a+1 , a+n+1  );
    build(1,1,n);
    int x1,x2,y1,y2;
    scanf("%d",&m);
    while(m--){
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        x1 = lower_bound( x.begin() , x.end() , x1 ) - x.begin() + 1;
        x2 = upper_bound( x.begin() , x.end() , x2 ) - x.begin();
        printf("%d\n",query(1,1,n,x1,x2,y1,y2) );
    }
    return 0;
}