Cod sursa(job #3306190)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 8 august 2025 14:00:28
Problema Zoo Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.32 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int n, tt;
pair<int, int> v[16010];
vector<int> auxLin, auxCol;
int rez[100010], maxLin;
int aint[4 * 116000 + 3];

struct Iris {
    int y, x1, x2;
    int index; ///sa stiu la ce dreptunghi actualizez
    bool tip; ///0 = punct ; 1 = linie de dreptunghi
    bool capat; ///doar pt dreptunghiuri, 0 = incepe(-) ; 1 = se termina(+)
};
vector<Iris> event;

inline int cmp(Iris a, Iris b) {
    if(a.y != b.y) return a.y < b.y;
    return a.tip < b.tip; ///procesez mai intai punctele
}

struct dreptunghi {
    int x1, y1, x2, y2;
}raw[100010];

inline void update(int nod, int st, int dr, int poz, int val) {
    if(st == dr) aint[nod] += val;
    else {
        int mid = (st + dr) / 2;
        if(poz <= mid) update(2 * nod, st, mid, poz, val);
        else update(2 * nod + 1, mid + 1, dr, poz, val);
        aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
    }
}

inline int query(int nod, int st, int dr, int a, int b) {
    if(a <= st && dr <= b) return aint[nod];
    else if(a > dr || b < st) return 0;
    else {
        int mid = (st + dr) / 2;
        return query(2 * nod, st, mid, a, b) + query(2 * nod + 1, mid + 1, dr, a, b);
    }
}

int main()
{
    fin >> n;
    for(int i=1; i<=n; i++) {
        fin >> v[i].first >> v[i].second;
        auxLin.push_back(v[i].first);
        auxCol.push_back(v[i].second);
    }
    fin >> tt;
    for(int i=1; i<=tt; i++) {
        fin >> raw[i].x1 >> raw[i].y1 >> raw[i].x2 >> raw[i].y2;
        auxLin.push_back(raw[i].x1);
        auxLin.push_back(raw[i].x2);
        auxCol.push_back(raw[i].y1);
        auxCol.push_back(raw[i].y2);
    }
    sort(auxLin.begin(), auxLin.end());
    vector<int>::iterator it = unique(auxLin.begin(), auxLin.end());
    auxLin.resize(distance(auxLin.begin(), it));
    sort(auxCol.begin(), auxCol.end());
    it = unique(auxCol.begin(), auxCol.end());
    auxCol.resize(distance(auxCol.begin(), it));
    for(int i=1; i<=n; i++) {
        v[i].first = lower_bound(auxLin.begin(), auxLin.end(), v[i].first) - auxLin.begin() + 1;
        v[i].second = lower_bound(auxCol.begin(), auxCol.end(), v[i].second) - auxCol.begin() + 1;
        event.push_back({v[i].second, v[i].first, v[i].first, -1, 0, 0});
        maxLin = max(maxLin, v[i].first);
    }
    for(int i=1; i<=tt; i++) {
        raw[i].x1 = lower_bound(auxLin.begin(), auxLin.end(), raw[i].x1) - auxLin.begin() + 1;
        raw[i].x2 = lower_bound(auxLin.begin(), auxLin.end(), raw[i].x2) - auxLin.begin() + 1;
        raw[i].y1 = lower_bound(auxCol.begin(), auxCol.end(), raw[i].y1) - auxCol.begin() + 1;
        raw[i].y2 = lower_bound(auxCol.begin(), auxCol.end(), raw[i].y2) - auxCol.begin() + 1;
        event.push_back({raw[i].y1 - 1, raw[i].x1, raw[i].x2, i, 1, 0});
        event.push_back({raw[i].y2, raw[i].x1, raw[i].x2, i, 1, 1});
        maxLin = max(maxLin, raw[i].x2);
    }
    sort(event.begin(), event.end(), cmp);
    for(Iris i : event) {
        if(i.tip == 0) update(1, 1, maxLin, i.x1, 1);
        else {
            if(i.capat == 0) rez[i.index] -= query(1, 1, maxLin, i.x1, i.x2);
            else rez[i.index] += query(1, 1, maxLin, i.x1, i.x2);
        }
    }
    for(int i=1; i<=tt; i++) fout << rez[i] << '\n';

    return 0;
}