Cod sursa(job #1467028)

Utilizator BLz0rDospra Cristian BLz0r Data 2 august 2015 17:08:05
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

#define Nmax 16002
#define x first
#define y second
#define L(x) ((x) << 1)
#define R(x) ((x) << 1) + 1

FILE *f = fopen ( "zoo.in", "r" );
FILE *g = fopen ( "zoo.out", "w" );

pair < int, int > v[Nmax];
vector < int > Aint[4*Nmax];

int N, M, X1, Y1, X2, Y2;

void BuildArb ( int nod, int st, int dr ){

    if ( st == dr ){
        Aint[nod].push_back ( v[st].y );
        return;
    }

    int mid = ( st + dr ) >> 1;

    BuildArb ( L(nod), st, mid );
    BuildArb ( R(nod), mid+1, dr );

    Aint[nod].resize ( Aint[L(nod)].size() + Aint[R(nod)].size() );
    merge ( Aint[L(nod)].begin(), Aint[L(nod)].end(), Aint[R(nod)].begin(), Aint[R(nod)].end(), Aint[nod].begin() );
}

int Query ( int nod, int st, int dr ){

    if ( X1 <= v[st].x && v[dr].x <= X2 ){
        int Left  = lower_bound ( Aint[nod].begin(), Aint[nod].end(), Y1 ) - Aint[nod].begin();
        int Right = upper_bound ( Aint[nod].begin(), Aint[nod].end(), Y2 ) - Aint[nod].begin();
        return Right - Left;
    }

    if ( st == dr )
        return 0;

    int rez = 0, mid = ( st + dr ) >> 1;

    if ( X1 <= v[mid].x )
        rez += Query ( L(nod), st, mid );
    if ( X2 >= v[mid+1].x )
        rez += Query ( R(nod), mid+1, dr );

    return rez;
}

int main(){

    fscanf ( f, "%d", &N );

    for ( int i = 1; i <= N; ++i ){
        fscanf ( f, "%d%d", &X1, &Y1 );
        v[i] = make_pair( X1, Y1 );
    }

    sort ( v+1, v+N+1 );
    BuildArb( 1, 1, N );

    fscanf ( f, "%d", &M );

    while ( M-- ){
        fscanf ( f, "%d%d%d%d", &X1, &Y1, &X2, &Y2 );
        fprintf ( g, "%d\n", Query ( 1, 1, N ) );
    }

    return 0;
}