Cod sursa(job #3294585)

Utilizator stefan_dore_Stefan Dore stefan_dore_ Data 25 aprilie 2025 20:22:02
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

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

const int NMAX = 16000;
int N, M, U[NMAX+1];

struct punct {
    int x, y;
};

punct P[NMAX+1];

vector<int> L[NMAX+1];
vector<int> Ai[4*NMAX+1];

bool cmp(const punct &a, const punct &b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

void interclasare(int rad) {
    int n = Ai[2*rad].size()-1, m = Ai[2*rad+1].size()-1, i = 0, j = 0;
    //
    while (i <= n && j <= m) {
        if (Ai[2*rad][i] <= Ai[2*rad+1][j]) {
            Ai[rad].push_back(Ai[2*rad][i]);
            i++;
        } else {
            Ai[rad].push_back(Ai[2*rad+1][j]);
            j++;
        }
    }
    //
    while (i <= n) {
        Ai[rad].push_back(Ai[2*rad][i]);
        i++;
    }
    //
    while (j <= m) {
        Ai[rad].push_back(Ai[2*rad+1][j]);
        j++;
    }
}

void Build(int rad, int st, int dr) {
    if (st == dr)
        swap(Ai[rad], L[st]);
    else {
        int m = (st + dr) / 2;
        //
        Build(2*rad, st, m);
        Build(2*rad+1, m+1, dr);
        //
        interclasare(rad);
    }
}

int findClosest(int rad, int val) {
    int p = 0, u = Ai[rad].size()-1, poz = -1;
    //
    while(p <= u) {
        int m = (p+u)/2;
        //
        if (Ai[rad][m] >= val) {
            poz = m;
            u = m - 1;
        } else
            p = m + 1;
    }
    //
    return poz;
}

int findFurthest(int rad, int val) {
    int p = 0, u = Ai[rad].size()-1, poz = -1;
    //
    while(p <= u) {
        int m = (p+u)/2;
        //
        if (Ai[rad][m] <= val) {
            poz = m;
            p = m + 1;
        } else
            u = m - 1;
    }
    //
    return poz;
}


int points(int rad, int y1, int y2) {
    int poz1 = findClosest(rad, y1),
        poz2 = findFurthest(rad, y2);
    //
    if (poz1 == -1 || poz2 == -1)
        return 0;
    //
    return poz2 - poz1 + 1;
}

int Query(int rad, int st, int dr, int a, int b, int y1, int y2) {
    if (a <= st && b >= dr)
        return points(rad, y1, y2);
    else {
        int m = (st + dr) / 2,
            r1 = 0, r2 = 0;
        //
        if (a <= m) r1 = Query(2*rad, st, m, a, b, y1, y2);
        if (b > m) r2 = Query(2*rad+1, m+1, dr, a, b, y1, y2);
        //
        return r1+r2;
    }
}

int normCloser(int val) {
    int p = 1, u = N, poz = -1;
    //
    while(p <= u) {
        int m = (p+u)/2;
        //
        if (U[m] >= val) {
            poz = m;
            u = m - 1;
        } else
            p = m + 1;
    }
    //
    return poz;
}

int normFurther(int val) {
    int p = 1, u = N, poz = -1;
    //
    while(p <= u) {
        int m = (p+u)/2;
        //
        if (U[m] <= val) {
            poz = m;
            p = m + 1;
        } else
            u = m - 1;
    }
    //
    return poz;
}

int main(){
    f >> N;
    for (int i=1; i<=N; i++)
        f >> P[i].x >> P[i].y;
    //
    sort(P+1, P+N+1, cmp);
    //
    int indx = 0;
    L[++indx].push_back(P[1].y);
    U[indx] = P[1].x;
    for (int i=2; i<=N; i++) {
        if (P[i].x != P[i-1].x) {
            indx++;
            U[indx] = P[i].x;
        }
        //
        L[indx].push_back(P[i].y);
    }
    //
    N = indx;
    Build(1, 1, N);
    //
    f >> M;
    int x1, y1, x2, y2;
    while (M--) {
        f >> x1 >> y1 >> x2 >> y2;
        //
        x1 = normCloser(x1);
        x2 = normFurther(x2);
        //
        if (x1 == -1 || x2 == -1) {
            g << 0 << '\n';
            continue;
        }
        //
        g << Query(1, 1, N, x1, x2, y1, y2) << '\n';
    }
    //
    f.close();
    g.close();
    return 0;
}