Cod sursa(job #3306065)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 7 august 2025 11:36:11
Problema Zoo Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.28 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 maxLin, maxCol;
vector<vector<unsigned short>> aib;

inline void update(int x, int y, int val) {
    for(int i=x; i<=maxLin; i+=(i&(-i)))
        for(int j=y; j<=maxCol; j+=(j&(-j))) aib[i][j] += val;
}

inline int query(int x, int y) {
    int rez = 0;
    for(int i=x; i>=1; i-=(i&(-i)))
        for(int j=y; j>=1; j-=(j&(-j))) rez += aib[i][j];
    return rez;
}

inline int querySubmatrice(int x1, int y1, int x2, int y2) { return query(x2, y2) - query(x2, y1 - 1) - query(x1 - 1, y2) + query(x1 - 1, y1 - 1); }

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);
    }
    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;
        maxLin = max(maxLin, v[i].first);
        maxCol = max(maxCol, v[i].second);
    }
    aib.assign(maxLin + 1, vector<unsigned short>(maxCol + 1, 0));
    for(int i=1; i<=n; i++) update(v[i].first, v[i].second, 1);
    fin >> tt;
    while(tt--) {
        int x1, y1, x2, y2; fin >> x1 >> y1 >> x2 >> y2;
        if(x1 >= maxLin) x1 = maxLin;
        else x1 = lower_bound(auxLin.begin(), auxLin.end(), x1) - auxLin.begin() + 1;
        if(y1 >= maxCol) y1 = maxCol;
        else y1 = lower_bound(auxCol.begin(), auxCol.end(), y1) - auxCol.begin() + 1;
        if(x2 >= maxLin) x2 = maxLin;
        else x2 = lower_bound(auxLin.begin(), auxLin.end(), x2) - auxLin.begin() + 1;
        if(y2 >= maxCol) y2 = maxCol;
        else y2 = lower_bound(auxCol.begin(), auxCol.end(), y2) - auxCol.begin() + 1;
        fout << querySubmatrice(x1, y1, x2, y2) << '\n';
    }

    return 0;
}