Cod sursa(job #2448256)

Utilizator Briana_NeaguNeagu Briana Briana_Neagu Data 16 august 2019 13:31:26
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.7 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';
   }
}