Cod sursa(job #1219602)

Utilizator xtreme77Patrick Sava xtreme77 Data 14 august 2014 17:36:33
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.19 kb
#include <fstream>
#include <algorithm>

#define pb push_back
#define f first
#define s second

const char IN [ ] = "zoo.in" ;
const char OUT [ ] = "zoo.out" ;
const int MAX = 16014 ;

using namespace std ;

ifstream fin ( IN ) ;
ofstream fout ( OUT ) ;

typedef pair < int , int > P ;

P a [ MAX ] ;
vector < int > v [ 20 * MAX ] , coordx ;
int RASP ;

void build ( int nod , int st , int dr )
{
    if ( st == dr )
    {
        v[nod].assign ( 1 , a [ st ].s );
        return ;
    }
    int mij = ( st + dr ) >> 1 ;
    build ( nod << 1 , st , mij ) ;
    build ( (nod << 1) + 1 , mij + 1 , dr ) ;
    v [ nod ].resize ( v [ nod << 1 ].size ( ) + v [ (nod << 1) + 1 ].size ( ) ) ;
    merge ( v [ nod << 1 ].begin ( ) , v [ nod << 1 ].end ( ) , v [ (nod << 1) + 1].begin ( ) , v [ (nod << 1) + 1].end ( ) , v [ nod ].begin ( ) ) ;
}

int query ( int nod , int st ,int dr ,int x1 , int y1 , int x2 , int y2 )
{
    if ( x1 <= st and dr <= x2 )
    {
        int SOL = upper_bound ( v [ nod ].begin ( ) , v [ nod ].end ( ) , y2 ) - v [ nod ].begin( ) ;
        int sol = lower_bound ( v [ nod ].begin ( ) , v [ nod ].end ( ) , y1 ) - v [ nod ].begin( ) ;
        return SOL - sol ;
    }
    if ( st == dr )
        return 0 ;
    int mij = ( st + dr ) >> 1 , RASP = 0 ;
    if ( x1 <= mij )
        RASP = RASP + query ( nod << 1 , st , mij , x1 , y1 , x2 , y2 ) ;
    if ( x2 > mij )
        RASP = RASP + query ( ( nod << 1 ) + 1 , mij + 1 , dr , x1 , y1 , x2 , y2 ) ;
    return RASP ;
}

int main ( )
{
    int n ;
    fin >> n ;
    for ( int i = 1 ; i <= n ; ++ i )
    {
        fin >> a [ i ].f >> a [ i ].s;
        coordx.pb  ( a[ i ].f ) ;
    }
    sort ( a + 1 , a + n + 1 );
    sort ( coordx.begin( ) ,coordx.end( ) ) ;
    build ( 1 , 1 , n ) ;
    int m ;
    fin >> m ;
    for ( ; m ; -- m )
    {
        int x1 , y1 , x2 , y2 ;
        fin >> x1 >> y1 >> x2 >> y2 ;
        x1 = lower_bound ( coordx.begin ( ) , coordx.end ( ) , x1 ) - coordx.begin ( ) + 1 ;
        x2 = upper_bound ( coordx.begin ( ) , coordx.end ( ) , x2 ) - coordx.begin ( ) ;
        fout << query ( 1 , 1 , n , x1 , y1 , x2 , y2 ) << '\n';
     }
    return 0 ;
}