Cod sursa(job #2002690)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 20 iulie 2017 16:45:08
Problema Zoo Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include<fstream>
#include<vector>
#include<algorithm>
using namespace std;
ifstream in("zoo.in");
ofstream out("zoo.out");
const int DIM = 16005;
pair<int,int>v[DIM];
int puncte,i,m;
struct str{
    vector< pair<int,int> >coord; int mini,maxi;
}aint[4*DIM];
void build( int nod, int st, int dr ){
    if( st == dr){
        aint[nod].coord.push_back( make_pair( v[st].first,v[st].second) );
        aint[nod].maxi = v[st].second;
        aint[nod].mini = v[st].second;
        return;
    }
    int mid = ( st + dr )>>1;
    build( nod << 1, st ,mid );
    build( nod<<1|1, mid+1,dr);
    aint[nod].mini = min( aint[nod<<1].mini,aint[nod<<1|1].mini );
    aint[nod].maxi = max( aint[nod<<1].maxi,aint[nod<<1|1].maxi );
    for( int i = 0; i < aint[nod<<1].coord.size(); i ++ ){
        aint[nod].coord.push_back( aint[nod<<1].coord[i]);
    }
    for( int i = 0; i < aint[nod<<1|1].coord.size(); i ++ ){
        aint[nod].coord.push_back( aint[nod<<1].coord[i]);
    }
    return;
}
int query( int nod, int x1, int y1, int x2, int y2 ){
    if( aint[nod].mini  >  x2 || aint[nod].maxi < x1 ){
        return 0;
    }
    if( aint[nod].mini >= x1 && aint[nod].maxi <= x2 ){
        int st, dr, mid;
        for( st = 0, dr = aint[nod].coord.size() - 1; st <= dr; ){
            int mid = ( st + dr ) >> 1;
            if( aint[nod].coord[mid].first < y1  ){
                st = mid + 1;
            }
            else{
                dr = mid - 1;
            }
        }
        int a  = st;
        for(  st = 0, dr = aint[nod].coord.size() - 1; st <= dr; ){
            int mid = ( st + dr ) >> 1;
            if( aint[nod].coord[mid].first <= y2 ){
                st = mid + 1;
            }
            else{
                dr = mid - 1;
            }
        }
        int b = dr;
        return  b - a + 1;
    }
    int stanga = query( nod << 1,x1,y1,x2,y2 );
    int dreapta =query( nod << 1|1, x1,y1,x2,y2 );
    return stanga + dreapta;
}
int main( void ){
    in >> puncte;
    for( i = 1; i <= puncte; i ++ ){
        in >> v[i].second >> v[i].first;
    }
    build(1,1,puncte);
    sort( v + 1, v + puncte + 1 );
    in >> m;
    int a1,a2,a3,a4;
    for( i = 1; i <= m ; i ++ ){
        in >> a1 >> a2 >> a3 >> a4;
        out<< query( 1,a1,a2,a3,a4 )<<"\n";
    }
    return 0;
}