Cod sursa(job #2461043)

Utilizator Teo_1101Mititelu Teodor Teo_1101 Data 24 septembrie 2019 20:37:54
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define x first
#define y second

using namespace std;

const int NMAX = 16001;
const int MMAX = 100001;

typedef pair <int, int> pii;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

int N, M;

pii A[NMAX];

struct zoo
{
    int x1, y1, x2, y2;
}Z[NMAX];

int F[MMAX*4 + NMAX*2];

vector < int > C;


int CB( int val, int lf, int rg )
{
    int mid = lf + ( rg - lf )/2;

    if( F[mid] == val ) return mid;

    if( F[mid] > val ) return CB(val, lf, mid - 1);
    else return CB( val, mid + 1, rg );
}
void Read()
{
    fin >> N;
    for( int i = 1; i <= N; ++i )
    {
        fin >> A[i].x >> A[i].y;
        C.push_back( A[i].x );
        C.push_back( A[i].y );

    }
    fin >> M;
    for( int i = 1; i <= M; ++i )
    {
        fin >> Z[i].x1 >> Z[i].y1 >> Z[i].x2 >> Z[i].y2;
        C.push_back( Z[i].x1 );
        C.push_back( Z[i].y1 );
        C.push_back( Z[i].x2 );
        C.push_back( Z[i].y2 );
    }

    sort( C.begin(), C.end());

    int val = -2000000001;

    for( int i = 0; i < C.size(); ++i )
    {
        if( C[i] != val )
        {
            val = C[i];
            F[0]++;
            F[F[0]] = C[i];
        }
    }

    //for( int i = 1; i <= F[0]; ++i ) fout << i << ' ' << F[i] << '\n';

    for( int i = 1; i <= N; ++i )
    {
        A[i].x = CB( A[i].x, 1, F[0] );
        A[i].y = CB( A[i].y, 1, F[0] );

        //fout << A[i].x << ' ' << A[i].y << '\n';
    }

    for( int i = 1; i <= M; ++i )
    {
        Z[i].x1 = CB( Z[i].x1, 1, F[0]);
        Z[i].y1 = CB( Z[i].y1, 1, F[0]);
        Z[i].x2 = CB( Z[i].x2, 1, F[0]);
        Z[i].y2 = CB( Z[i].y2, 1, F[0]);

        //fout << Z[i].x1 << Z[i].y1 << Z[i].x2 << Z[i].y2;
    }
}

void Do()
{
    for( int i = 1; i <= M; ++i )
    {
        int nr = 0;
        for( int j = 1; j <= N; ++j )
        {
            if( A[j].x >= Z[i].x1 && A[j].x <= Z[i].x2 && A[j].y >= Z[i].y1 && A[j].y <= Z[i].y2 ) nr++;
        }
        fout << nr << '\n';
    }
}
int main()
{
    Read();
    Do();
    return 0;
}