Cod sursa(job #3166349)

Utilizator Chris_BlackBlaga Cristian Chris_Black Data 8 noiembrie 2023 16:53:46
Problema Zoo Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <iostream>
#include <vector>
#include <algorithm>
#define VI vector<int>
#define VVI vector<VI>
#define PI pair<int, int>
#define F first
#define S second
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define FORR(i, a, b) for(int i = a; i >= b; --i)
#define pb push_back
#define ll long long
#define All(v) v.begin(), v.end()

using namespace std;
const int N = 16009, M = 1e5 + 9;

int n, m;
struct query
{
    int x1, y1, x2, y2;
};
query animals[N], queries[M];

VI norm;
VVI v;

void Normalize()
{
    /// Sunt indexate de la 0!!!

    sort(norm.begin(), norm.end());
    norm.erase(unique(norm.begin(), norm.end()), norm.end());

    FOR(i, 1, n)animals[i].x1 = distance(norm.begin(), lower_bound(norm.begin(), norm.end(), animals[i].x1));
    FOR(i, 1, m)
    {
        queries[i].x1 = distance(norm.begin(), lower_bound(norm.begin(), norm.end(), queries[i].x1));
        queries[i].x2 = distance(norm.begin(), lower_bound(norm.begin(), norm.end(), queries[i].x2));
    }
}

VVI tree;
void Build(int nod = 1, int st = 0, int dr = norm.size() - 1)
{
    if(st == dr)
    {
        tree[nod] = v[st];
        return;
    }
    int mij = (st + dr) >> 1;
    Build(nod << 1, st, mij);
    Build(nod << 1 | 1, mij + 1, dr);

    merge(begin(tree[nod << 1]), end(tree[nod << 1]),
          begin(tree[nod << 1 | 1]), end(tree[nod << 1 | 1]),
            back_inserter(tree[nod]));
}
int Query(int x1, int x2, int y1, int y2, int nod = 1, int st = 0, int dr = norm.size() - 1)
{
    if(x1 <= st && dr <= x2)
        return distance(upper_bound(All(tree[nod]), y1 - 1), lower_bound(All(tree[nod]), y2 + 1));
    int mij = (st + dr) >> 1;
    if(x2 <= mij)return Query(x1, x2, y1, y2, nod << 1, st, mij);
    else if(x1 > mij)return Query(x1, x2, y1, y2, nod << 1 | 1, mij + 1, dr);
    return Query(x1, x2, y1, y2, nod << 1, st, mij) + Query(x1, x2, y1, y2, nod << 1 | 1, mij + 1, dr);
}

int main()
{
    cin >> n;

    FOR(i, 1, n)
    {
        cin >> animals[i].x1 >> animals[i].y1;
        norm.pb(animals[i].x1);
    }

    cin >> m;
    FOR(i, 1, m)
    {
        cin >> queries[i].x1 >> queries[i].y1 >> queries[i].x2 >> queries[i].y2;
        norm.pb(animals[i].x1);
        norm.pb(animals[i].x2);
    }


    Normalize();

    v = VVI(norm.size());
    FOR(i, 1, n)
        v[animals[i].x1].pb(animals[i].y1);
    FOR(i, 1, n)
        sort(v[animals[i].x1].begin(), v[animals[i].x1].end());

    tree = VVI(norm.size() * 4 + 9);
    Build();

    FOR(i, 1, m)
    {
        query q = queries[i];
        cout << Query(q.x1, q.x2, q.y1, q.y2) << '\n';
    }
    return 0;
}