Cod sursa(job #2546232)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 13 februarie 2020 21:58:23
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMAX = 16000;

int N, M;
pair <int, int> v[NMAX + 5];
vector <int> tree[4 * NMAX];

struct ArbInt
{
    void Build(int node, int st, int dr)
    {
        if(st == dr)
        {
            tree[node].push_back(v[st].second);
            return ;
        }

        int mid = (st + dr) / 2;

        Build(2 * node, st, mid);
        Build(2 * node + 1, mid + 1, dr);

        tree[node].resize(tree[2 * node].size() + tree[2 * node + 1].size());

        merge(tree[2 * node].begin(), tree[2 * node].end(),
              tree[2 * node + 1].begin(), tree[2 * node + 1].end(),
              tree[node].begin());
    }

    int Query(int node, int st, int dr, int l, int r, int y1, int y2)
    {
        if(r < st || l > dr)
            return 0;

        if(l <= st && dr <= r)
        {
            auto p1 = upper_bound(tree[node].begin(), tree[node].end(), y2);
            auto p2 = lower_bound(tree[node].begin(), tree[node].end(), y1);

            return p1 - p2;
        }

        int sum = 0;
        int mid = (st + dr) / 2;

        if(l <= mid)
            sum += Query(2 * node, st, mid, l, r, y1, y2);

        if(r > mid)
            sum += Query(2 * node + 1, mid + 1, dr, l, r, y1, y2);

        return sum;
    }
};

ArbInt aint;

int bs1(int val)
{
    int sol = 0;
    int st = 1, dr = N, mid;

    while(st <= dr)
    {
        mid = (st + dr) / 2;

        if(v[mid].first >= val)
            dr = mid - 1;
        else
        {
            sol = mid;
            st = mid + 1;
        }
    }
    return sol;
}

int bs2(int val)
{
    int sol = N + 1;
    int st = 1, dr = N, mid;

    while(st <= dr)
    {
        mid = (st + dr) / 2;

        if(v[mid].first <= val)
            st = mid + 1;
        else
        {
            sol = mid;
            dr = mid - 1;
        }
    }
    return sol;
}

int main()
{
    fin >> N;

    for(int i = 1; i <= N; i++)
        fin >> v[i].first >> v[i].second;

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

    aint.Build(1, 1, N);

    fin >> M;

    for(int i = 1; i <= M; i++)
    {
        int x1, x2, y1, y2;
        fin >> x1 >> y1 >> x2 >> y2;

        if(x1 > v[N].first || x2 < v[1].first)
            fout << "0\n";
        else
        {
            int l = bs1(x1) + 1;
            int r = bs2(x2) - 1;

            fout << aint.Query(1, 1, N, l, r, y1, y2) << '\n';
        }
    }

    return 0;
}