Cod sursa(job #3341887)

Utilizator BuzdiBuzdugan Rares Andrei Buzdi Data 21 februarie 2026 14:08:20
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <bits/stdc++.h>
#define ll long long

using namespace std;

ifstream fin("zoo.in");
ofstream fout("zoo.out");

const int NMAX = 16'000;
const int MMAX = 1e5;

int n, m, ID, ind;
map<int, int> mp;
int answer[MMAX + 1];
vector<int> v;

struct Event {
    int type, x, y1, y2, qind;
    bool operator < (const Event& other) const {
        if(x != other.x) {
            return x < other.x;
        }
        return type < other.type;
    }
}events[3 * MMAX + 1];

struct AIB {
    int n;
    int aib[3 * MMAX + 1];

    void init(int n) {
        this->n = n;
        fill(aib + 1, aib + n + 1, 0);
    }

    void update(int pos, int value) {
        for(int i = pos; i <= n; i += i & (-i)) {
            aib[i] += value;
        }
    }

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

int main() {
    fin >> n;
    for(int i = 1; i <= n; i++) {
        int x, y;
        fin >> x >> y;

        v.push_back(y);

        events[++ind] = {0, x, y, y, 0};
    }

    fin >> m;
    for(int i = 1; i <= m; i++) {
        int x1, y1, x2, y2;
        fin >> x1 >> y1 >> x2 >> y2;

        v.push_back(y1);
        v.push_back(y2);

        events[++ind] = {1, x2, y1, y2, i};
        events[++ind] = {2, x1 - 1, y1, y2, i};
    }

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

    sort(events + 1, events + ind + 1);
    aib.init(v.size());
    for(int i = 1; i <= ind; i++) {
        auto [type, x, y1, y2, qind] = events[i];
        y1 = lower_bound(v.begin(), v.end(), y1) - v.begin() + 1;
        y2 = lower_bound(v.begin(), v.end(), y2) - v.begin() + 1;

        if(type == 0) {
            aib.update(y1, 1);
        }
        else {
            int sign = (type == 1 ? 1 : -1);
            answer[qind] += (aib.query(y2) - aib.query(y1 - 1)) * sign;
        }
    }

    for(int i = 1; i <= m; i++) {
        fout << answer[i] << '\n';
    }
    return 0;
}