Cod sursa(job #3351001)

Utilizator Andrei-Dani-10Pisla Andrei Daniel Andrei-Dani-10 Data 15 aprilie 2026 16:48:19
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3 kb
#include <fstream>

#include <utility>
#define x first
#define y second

#include <algorithm>

#include <vector>

using namespace std;

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

typedef pair <int, int> pii;
const int nmax = 16000, qmax = 2e5;
int n, nrq, xx, yy, lff, rgg, answer[qmax + 2]; pii a[nmax + 2];

/// ---> normalize by y to have fenwick tree over points <--- ///
pii norm[nmax + 2]; int actually[nmax + 2], nvs;

void getnormalizedy(){
    for(int i = 1; i <= n; i++){
        norm[i] = make_pair(a[i].y, i);
    }

    norm[0].x = (1 << 31) + 1;
    sort(norm + 1, norm + 1 + n);

    for(int i = 1; i <= n; i++){
        nvs += (norm[i].x != norm[i - 1].x);
        actually[nvs] = norm[i].x; a[norm[i].y].y = nvs;
    }

    return;
}

int getlefttpointt(int xx){
    int st = 1, dr = nvs, mij, bestt = -1;

    for(; st <= dr; ){
        mij = (st + dr) >> 1;
        if(xx <= actually[mij]){
            bestt = mij, dr = mij - 1;
        }else{ st = mij + 1; }
    }

    return bestt;
}

int getrighttpointt(int xx){
    int st = 1, dr = nvs, mij, bestt = -1;

    for(; st <= dr; ){
        mij = (st + dr) >> 1;
        if(actually[mij] <= xx){
            bestt = mij, st = mij + 1;
        }else{ dr = mij - 1; }
    }

    return bestt;
}

struct query{
    int heightt, leftt, rightt, qidx, sign;

    query(int hh, int lff, int rgg, int idx, int sgn) :
        heightt(hh), leftt(lff), rightt(rgg), qidx(idx), sign(sgn) {};

    bool operator < (const query &obj) const {
        return heightt < obj.heightt;
    }
}; vector <query> queries;

inline int f(int x){ return (x & (-x)); }
struct fenwicktree{
    int tree[nmax + 2];

    void updateadd(int node, int vall){
        for(int i = node; i <= nvs; i += f(i)){
            tree[i] += vall;
        }
        return;
    }

    int query(int node){
        int summ = 0;
        for(int i = node; i >= 1; i -= f(i)){
            summ += tree[i];
        }
        return summ;
    }
} myaib;

int main(){

    in>>n;
    for(int i = 1; i <= n; i++){
        in>>a[i].x>>a[i].y;
    }

    getnormalizedy();

    in>>nrq; queries.reserve(2 * nrq);
    for(int itq = 1; itq <= nrq; itq++){
        in>>xx>>lff>>yy>>rgg;
        lff = getlefttpointt(lff);
        rgg = getrighttpointt(rgg);

        if(lff == -1 || rgg == -1){ continue; }

        queries.push_back(query(xx - 1, lff, rgg, itq, -1));
        queries.push_back(query(yy, lff, rgg, itq, +1));
    }

    sort(queries.begin(), queries.end());
    sort(a + 1, a + 1 + n); ///sweep line

    int idx = 1;
    for(auto qry : queries){
        for(; idx <= n && a[idx].x <= qry.heightt; ){
            myaib.updateadd(a[idx].y, +1); idx++;
        }

        answer[qry.qidx] -= qry.sign * myaib.query(qry.leftt - 1);
        answer[qry.qidx] += qry.sign * myaib.query(qry.rightt);
    }

    for(int itq = 1; itq <= nrq; itq++){
        out<<answer[itq]<<"\n";
    }

    return 0;
}