Cod sursa(job #2448399)

Utilizator Carol_LucaCarol Luca Carol_Luca Data 16 august 2019 20:23:01
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.15 kb
#include <bits/stdc++.h>

#define maxi 16005



using namespace std;



ifstream f("zoo.in");

ofstream g("zoo.out");



struct cor

{

    int x, y;

};



vector <int> tree[maxi << 2], xs;

vector <cor> pet;



int getMin(int i, int j, vector <int> &v, const int x)

{

    int ans = -1;

    while (i <= j)

    {

        int m = (i + j) / 2;

        if (v[m] >= x)

            j = m - 1;

        else

        {

            ans = m;

            i = m + 1;

        }

    }

    return ans;

}



int getMax(int i, int j, vector <int> &v, const int x)

{

    int ans = j + 1;

    while(i <= j)

    {

        int m = (i + j) / 2;

        if (v[m] <= x)

            i = m + 1;

        else

        {

            j = m - 1;

            ans = m;

        }

    }

    return ans;

}



bool mycmp(cor a, cor b)

{

    if (a.x == b.x)

        return a.y < b.y;

    return a.x < b.x;

}

void inter(int nod, int a, int b)

{

    int i = 0, j = 0;

    while (i < tree[a].size() && j < tree[b].size())

    {

        if (tree[a][i] < tree[b][j])

            tree[nod].push_back(tree[a][i ++]);

        else

            tree[nod].push_back(tree[b][j ++]);

    }

    while (i != tree[a].size())

        tree[nod].push_back(tree[a][i ++]);

    while (j != tree[b].size())

        tree[nod].push_back(tree[b][j ++]);



}

void create(int nod, int i, int j)

{

    assert(nod <= (maxi << 2));



    if (i == j)

        tree[nod].push_back(pet[i - 1]. y);

    else

    {

        int m = (i + j) / 2;

        create(nod * 2, i, m);

        create(nod * 2 + 1, m + 1, j);

        inter(nod, nod * 2, nod * 2 + 1);

    }

}



int query(int nod, int i, int j, const int a, const int b, const int min, const int max)

{

    assert(nod <= (maxi << 2));

    if (a <= i && b >= j)

    {



        int st = getMin(0, tree[nod].size() - 1, tree[nod], min);

        int dr = getMax(0, tree[nod].size() - 1, tree[nod], max);

        int ans =  dr - (st + 1);

        assert(ans >= 0);

        return ans;

    }

    int m = (i + j) / 2;

    int ans = 0;

    if (a <= m)

        ans += query(nod * 2, i, m, a, b, min, max);

    if (b > m)

        ans += query(nod * 2 + 1, m + 1, j, a, b, min, max);

    return ans;

}



int main()

{

    int n, m;

    f >> n;

    for (int i = 1; i <= n; ++ i)

    {

        int x, y;

        f >> x >> y;

        pet.push_back({x, y});

    }

    sort(pet.begin(), pet.end(), mycmp);

    for (auto el: pet)

        xs.push_back(el.x);

    create(1, 1, n);

    f >> m;

    while(m --)

    {

        int x1, x2, y1, y2;

        f >> x1 >> y1 >> x2 >> y2;



        //aici vad pe ce interval ma duc

        int minVal  = getMin(0, xs.size() - 1, xs, x1) + 2;

        int maxVal  = getMax(0, xs.size() - 1, xs, x2) ;

        if (minVal > maxVal)

            g << '0' << '\n';

        else

            g << query(1, 1, n, minVal, maxVal, y1, y2) << '\n';

    }

}