Cod sursa(job #2530151)

Utilizator mihneacazCazacu Mihnea mihneacaz Data 24 ianuarie 2020 14:18:17
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

const int NMAX = 100005;
const int ABS = 2 * (1e9);

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

pair <int, int> v[NMAX];
vector <int> tree[3 * NMAX];

int mylowerbound(int st, int dr, int x)
{
    int last = 0;
    while (st <= dr) {
        int med = (st + dr) / 2;
        if (v[med].first >= x)
            dr = med - 1;
        else {
            last = med;
            st = med + 1;
        }
    }
    return last;
}

int myupperbound(int st, int dr, int x)
{
    int last = dr + 1;
    while(st <= dr) {
        int med = (st + dr) / 2;
        if (v[med].first <= x)
            st = med + 1;
        else {
            last = med;
            dr = med - 1;
        }
    }
    return last;
}

void build(int node, int st, int dr)
{
    if(st == dr) {
        tree[node].emplace_back(v[st].second);
        return ;
    }
    int med = (st + dr) / 2;
    build(node * 2, st, med);
    build(node * 2 + 1, med + 1, dr);
    tree[node].resize(tree[node * 2].size() + tree[node * 2 + 1].size());
    merge(tree[node * 2].begin(), tree[node * 2].end(), tree[node * 2 + 1].begin(), tree[node * 2 + 1].end(), tree[node].begin());
}

int query(int node, int st, int dr, int left, int right, int y1, int y2)
{
    int sum = 0;
    if(left <= st && dr <= right) {
        auto aux1 = upper_bound(tree[node].begin(), tree[node].end(), y2);
        auto aux2 = lower_bound(tree[node].begin(), tree[node].end(), y1);
        return aux1 - aux2;
    }
    int med = (st + dr) / 2;
    if(left <= med)
        sum += query(node * 2, st, med, left, right, y1, y2);
    if(right > med)
        sum += query(node * 2 + 1, med + 1, dr, left, right, y1, y2);
    return sum;
}

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; ++i) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v + 1, v + n + 1);
    build(1, 1, n);
    int m;
    cin >> m;
    for(int i = 1; i <= m; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1 > v[n].first || x2 < v[1].first) {
            cout << "0\n";
        }
        else {
            int aux1 = mylowerbound(1, n, x1) + 1;
            int aux2 = myupperbound(1, n, x2) - 1;
            cout << query(1, 1, n, aux1, aux2, y1, y2) << "\n";
        }
    }
    return 0;
}