Cod sursa(job #3162149)

Utilizator YosifIosif Andrei Stefan Yosif Data 28 octombrie 2023 13:57:51
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.2 kb
#include <bits/stdc++.h>
using namespace std;

string file = "zoo";
ifstream fin(file + ".in");
ofstream fout(file + ".out");

int n, m;
pair <int, int> v[20001];
vector <int> t[100001];

void build(int i = 1, int l = 1, int r = n) {

    if (l == r) {

        t[i].resize(1);
        t[i][0] = v[l].second;
        return;
    }

    int m = (l + r) >> 1;
    int aux = (i << 1);

    build(aux, l, m);
    build(aux + 1, m + 1, r);

    vector <int>::iterator it1, it2;
    it1 = t[aux].begin();
    it2 = t[aux + 1].begin();

    while (it1 != t[aux].end() && it2 != t[aux + 1].end())
        if (*it1 < *it2)
            t[i].push_back(*it1), it1++;
        else
            t[i].push_back(*it2), it2++;

    while (it1 != t[aux].end())
        t[i].push_back(*it1), it1++;

    while (it2 != t[aux + 1].end())
        t[i].push_back(*it2), it2++;
}

int get(int x1, int y1, int x2, int y2, int i = 1, int l = 1, int r = n) {

    if (x2 < v[l].first || v[r].first < x1)
        return 0;

    if (x1 <= v[l].first && v[r].first <= x2) {

        int Left = 0, Right = t[i].size() - 1, pos1 = -1, pos2 = -1;

        while (Left <= Right) {

            int mid = (Left + Right) >> 1;

            if (t[i][mid] >= y1) {

                pos1 = mid;
                Right = mid - 1;
            }
            else
                Left = mid + 1;
        }

        if (pos1 == -1)
            return 0;

        Left = pos1;
        Right = t[i].size() - 1;

        while (Left <= Right) {

            int mid = (Left + Right) >> 1;

            if (t[i][mid] <= y2) {

                pos2 = mid;
                Left = mid + 1;
            }
            else
                Right = mid - 1;
        }

        if (pos2 == -1)
            return 0;

        return pos2 - pos1 + 1;
    }

    int m = (l + r) >> 1;

    return get(x1, y1, x2, y2, (i << 1), l, m) + get(x1, y1, x2, y2, (i << 1) + 1, m + 1, r);
}

int main() {

    fin >> n;

    for (int i = 1; i <= n; i++)
        fin >> v[i].first >> v[i].second;

    sort(v + 1, v + n + 1);
    build();

    fin >> m;

    for (int i = 1; i <= m; i++) {

        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;

        fout << get(x1, y1, x2, y2) << '\n';
    }

    return 0;
}