Cod sursa(job #2431826)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 20 iunie 2019 20:42:39
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.37 kb
#include <fstream>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

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

const int NMax = 16000;

vector <int> AIT[4 * NMax + 5]; pair <int, int> V[NMax + 5];
int N, M, x1, x2, y1, y2;

void Build(int i, int st, int dr)
{
    if(st == dr)
    {
        AIT[i].push_back(V[st].second);
        return;
    }
    int m = (st + dr) >> 1;

    Build(2 * i, st, m);
    Build(2 * i + 1, m + 1, dr);

    for(auto a : AIT[2 * i])
        AIT[i].push_back(a);

    for(auto a : AIT[2 * i + 1])
        AIT[i].push_back(a);

    sort(AIT[i].begin(), AIT[i].end());
}

int Querry(int i, int st, int dr)
{
    int a = V[st].first, b = V[dr].first, m = (st + dr) >> 1;

    if(x2 < a || b < x1)
        return 0;

    if(x1 <= a && b <= x2)
    {
        return upper_bound(AIT[i].begin(), AIT[i].end(), y2) -
               lower_bound(AIT[i].begin(), AIT[i].end(), y1);
    }
    return (Querry(2 * i, st, m) + Querry(2 * i + 1, m + 1, dr));
}

int main()
{
    fin >> N;

    for(int i = 1, a, b; i <= N; i++)
        fin >> a >> b, V[i] = {a, b};

    sort(V + 1, V + N + 1);
    Build(1, 1, N); fin >> M;

    while(M--)
    {
        fin >> x1 >> y1 >> x2 >> y2;
        fout << Querry(1, 1, N) << '\n';
    }
    fin.close();
    fout.close();

    return 0;
}