Cod sursa(job #871700)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 5 februarie 2013 02:09:36
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb

#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream in ("zoo.in");

const int N=16001;

pair<int,int> A[N];
vector<int> ADI[N<<2];
int n,m;
int X1,X2,Y1,Y2;

void READ ()
{

    in>>n;

    for(int i=1;i<=n;++i)
        in>>A[i].first>>A[i].second;

}

void MERGE (int n1)
{

    int n2=n1<<1;
    int n3=n2+1;
    size_t i=0,j=0,k=0;

    ADI[n1].resize( ADI[n2].size() + ADI[n3].size() );

    for( ; i < ADI[n2].size() && j < ADI[n3].size() ; ++k )
        if( ADI[n2][i] < ADI[n3][j] )
        {
            ADI[n1][k]=ADI[n2][i];
            ++i;
        }
        else
        {
            ADI[n1][k]=ADI[n3][j];
            ++j;
        }

    for( ; i < ADI[n2].size() ; ++i , ++k)
        ADI[n1][k]=ADI[n2][i];

    for( ; j < ADI[n3].size() ; ++j , ++k)
        ADI[n1][k]=ADI[n3][j];

}

void BUILD (int nod,int ft,int bk)
{

    if( ft == bk )
    {
        ADI[nod].push_back(A[ft].second);
        return;
    }

    int mid = (ft+bk)>>1 ;

    BUILD( nod<<1 , ft, mid );
    BUILD( (nod<<1)+1 , mid+1 , bk );
    MERGE (nod);

}

int QUERY (int nod,int ft,int bk,int L,int R)
{

    if( L <= A[ft].first && A[bk].first <= R )
        return lower_bound(ADI[nod].begin(),ADI[nod].end(),Y2+1)-lower_bound(ADI[nod].begin(),ADI[nod].end(),Y1);

    if( ft == bk )
        return 0;

    int mid = (ft+bk)>>1 ;

    if( R < A[mid+1].first )
        return QUERY ( nod<<1 , ft , mid , L , R );

    if( L > A[mid].first )
        return QUERY ( (nod<<1)+1 , mid+1, bk , L , R );

    int S1 = QUERY ( nod<<1 , ft , mid , L , A[mid].first );
    int S2 = QUERY ( (nod<<1)+1 , mid+1 , bk , A[mid+1].first , R );

    return S1+S2;

}

void OUT ()
{

    freopen ("zoo.out","w",stdout);

    for(in>>m;m;--m)
    {
        in>>X1>>Y1>>X2>>Y2;
        X1=max(X1,A[1].first);
        X2=min(X2,A[n].first);
        int SOL = QUERY ( 1 , 1 , n , X1 , X2 );
        printf("%d\n",SOL);
    }

}

int main ()
{

    READ ();
    sort ( A+1 , A+n+1 );
    BUILD ( 1 , 1 , n );
    OUT ();

    return 0;

}