Cod sursa(job #2740930)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 14 aprilie 2021 19:50:54
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.95 kb
#include <bits/stdc++.h>
#pragma GCC optimize("O3")

#define MOD 1000000007
using namespace std;

const int INF = (1 << 30), NMAX(100005);
using VI  = vector<int>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using Point = array<int, 2>;

void BUNA(const string& task = "")
{
    if (!task.empty())
        freopen((task + ".in").c_str(), "r", stdin),
                freopen((task + ".out").c_str(), "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
void PA()
{
    exit(0);
}

vector<int> Arb[4 * NMAX + 5];
Point p[NMAX];
void build(int nod, int st, int dr){
    for(int i = st; i <= dr; ++i)
        Arb[nod].push_back(p[i][1]);
    sort(Arb[nod].begin(), Arb[nod].end());
    int mij = (st + dr) / 2;
    if(st != dr){
        build(2 * nod, st, mij);
        build(2 * nod + 1, mij + 1, dr);
    }
}

int query(int st, int dr, int nod, int x1, int y1, int x2, int y2){
    if(st > x2 || x1 > dr)
        return 0;
    if(x1 <= st && dr <= x2){
        int p1 = upper_bound(Arb[nod].begin(), Arb[nod].end(), y1 - 1) - Arb[nod].begin();
        int p2 = upper_bound(Arb[nod].begin(), Arb[nod].end(), y2) - Arb[nod].begin() - 1;
        return p2 - p1 + 1;
    }
    int mij = (st + dr) / 2;
    return query(st, mij, 2 * nod, x1, y1, x2, y2) + query(mij + 1, dr, 2 * nod + 1, x1, y1, x2, y2);
}

int main()
{
    BUNA("zoo");
    int n;
    cin >> n;

    for(int i = 1; i <= n; ++i)
        cin >> p[i][0] >> p[i][1];

    sort(p + 1, p + n + 1);

    build(1, 1, n);

    int q;
    cin >> q;

    while(q--){
        Point a, b;
        cin >> a[0] >> a[1] >> b[0] >> b[1];

        Point aux;
        aux[0] = a[0], aux[1] = -(2e9);
        int x1 = upper_bound(p + 1, p + n + 1, aux) - p;
        aux[0] = b[0], aux[1] = -aux[1];
        int x2 = upper_bound(p + 1, p + n + 1, aux) - p - 1;
        cout << query(1, n, 1, x1, a[1], x2, b[1]) << '\n';
    }
    PA();
}