Cod sursa(job #2002682)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 20 iulie 2017 16:34:00
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 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,x1,y1,x2,y2;
struct str{
    vector< pair<int,int> >coord; int mini,maxi;
}aint[4*DIM];
str update_nod( str s1, str s2 ){
    str srez;
    srez.mini = min( s1.mini,s2.mini );
    srez.maxi = max( s1.maxi,s2.maxi );
    for( int i = 0; i < s1.coord.size(); i ++ ){
        srez.coord.push_back( s1.coord[i]);
    }
    for( int i = 0; i < s2.coord.size(); i ++ ){
        srez.coord.push_back( s2.coord[i]);
    }
    return srez;
}
void build( int nod, int st, int dr ){
    if( st == dr){
        aint[nod].coord.push_back( make_pair( v[st].second,v[st].first) );
        aint[nod].maxi = v[st].first;
        aint[nod].mini = v[st].first;
        return;
    }
    int mid = ( st + dr )>>1;
    build( nod << 1, st ,mid );
    build( nod<<1|1, mid+1,dr);
    aint[nod] = update_nod( aint[nod<<1], aint[nod<<1|1] );
    sort( aint[nod].coord.begin(), aint[nod].coord.end());
    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].first >> v[i].second;
    }
    build(1,1,puncte);
    sort( v + 1, v + puncte + 1 );
    in >> m;
    for( i = 1; i <= m ; i ++ ){
        in >> x1 >> y1 >> x2 >> y2;
        out<< query( 1,x1,y1,x2,y2 )<<"\n";
    }
    return 0;
}