Cod sursa(job #3039865)

Utilizator _andrei4567Stan Andrei _andrei4567 Data 28 martie 2023 22:32:32
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
///baleiere:)

#include <fstream>
#include <vector>
#include <algorithm>
#define lsb(x) x & (-x)
#define int long long

using namespace std;

ifstream cin ("zoo.in");
ofstream cout ("zoo.out");

const int  N = 16e3;
const int M = 1e5;
int rez[M + 1], aib[M * 3 + 2];

vector <int> normx, normy;

void update (int pos, int val)
{
    for (int i = pos; i <= 3 * M; i += lsb(i))
        aib[i] += val;
}

int query (int pos)
{
    int sum = 0;
    for (int i = pos; i >= 1; i -= lsb(i))
        sum += aib[i];
    return sum;
}

struct quer
{

    int x, y, yy, op, ind;
} v[M * 2 + 1];

struct points
{
    int x, y;
} a[N + 1];

int n, x, yy, xx, y, len, m;

signed main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[i].x >> a[i].y, normx.push_back(a[i].x), normy.push_back(a[i].y);
    cin >> m;
    for (int i = 1; i <= m; ++i)
    {
        cin >> x >> y >> xx >> yy;
        normx.push_back(x - 1);
        normx.push_back(xx);
        normy.push_back(y);
        normy.push_back(yy);
        v[++len] = {x - 1, y, yy, 1, i};
        v[++len] = {xx, y, yy, -1, i};

    }
    sort (normx.begin(), normx.end());
    sort (normy.begin(), normy.end());
    vector <int> :: iterator it = unique (normx.begin(), normx.end());
    normx.resize(distance (normx.begin(), it));
    vector <int> :: iterator it1 = unique (normy.begin(), normy.end());
    normy.resize(distance (normy.begin(), it1));
    for (int i = 1; i <= n; ++i)
    {
        a[i].x = lower_bound(normx.begin(), normx.end(), a[i].x) - normx.begin() + 1;
        a[i].y = lower_bound (normy.begin(), normy.end(), a[i].y) - normy.begin() + 1;
    }
    sort (a + 1, a + n + 1, [](const points &a, const points &b)
    {
        return a.x < b.x;
    });
    for (int i = 1; i <= len; ++i)
    {
        v[i].x = lower_bound(normx.begin(), normx.end(), v[i].x) - normx.begin() + 1;
        v[i].y = lower_bound(normy.begin(), normy.end(), v[i].y) - normy.begin() + 1;
        v[i].yy = lower_bound(normy.begin(), normy.end(), v[i].yy) - normy.begin() + 1;
    }
    sort (v + 1, v + len + 1, [](const quer &a, const quer &b)
    {
        if (a.x == b.x)return a.op < b.op;
        return a.x < b.x;
    });
    int p = 1;
    for (int i = 1; i <= len; ++i)
    {
        while (a[p].x <= v[i].x && p <= n)
        {
            update (a[p].y, 1);
            ++p;
        }
        if (v[i].op == 1)
            rez[v[i].ind] -= (query (v[i].yy) - query (v[i].y - 1));
        else
            rez[v[i].ind] += (query (v[i].yy) - query (v[i].y - 1));
    }
    for (int i = 1; i <= m; ++i)
        cout << rez[i] << '\n';
    return 0;
}