Cod sursa(job #3330752)

Utilizator Lex._.Lex Guiman Lex._. Data 21 decembrie 2025 19:46:11
Problema Zoo Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.99 kb
#include <bits/stdc++.h>
#define NMAX 16001
#define inf 2000000001
#define x first
#define y second
using namespace std;

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

int n, m;
vector<int> coord_x={-inf};
vector<vector<int>> coord_y;
pair<int, int> puncte[NMAX];

void unic(vector<int>& v) ///elimina elementele care apar de mai multe ori din vector
{
    int nr_unice=1;
    for(int i=1; i<v.size(); i++)
    {
        if(v[i]!=v[i-1]) v[nr_unice++]=v[i];
    }
    v.resize(nr_unice);
}

vector<vector<int>> aint;

void build(int nod, int st, int dr)
{
    if(st==dr)
    {
        aint[nod]=coord_y[st];
        //out << nod << " " << st << " " << dr << ": ";
        //for(auto j : aint[nod]) out << j << " "; out << "\n";
        return;
    }
    int mij=st+(dr-st)/2;
    build(nod*2, st, mij);
    build(nod*2+1, mij+1, dr);
    aint[nod].resize(aint[nod*2].size()+aint[nod*2+1].size());
    merge(aint[nod*2].begin(), aint[nod*2].end(), aint[nod*2+1].begin(), aint[nod*2+1].end(), aint[nod].begin());
    //out << nod << " " << st << " " << dr << ": ";
    //for(auto j : aint[nod]) out << j << " "; out << "\n";
}

int query(int x1, int y1, int x2, int y2, int nod, int st, int dr)
{
    if(x1<=st && dr<=x2)
    {
        //out << st << " " << dr << "   " << (lower_bound(aint[nod].begin(), aint[nod].end(), y1)-aint[nod].begin()) << " " << (upper_bound(aint[nod].begin(), aint[nod].end(), y2)-aint[nod].begin()) << "\n";
        return upper_bound(aint[nod].begin(), aint[nod].end(), y2)-lower_bound(aint[nod].begin(), aint[nod].end(), y1);
    }
    if(dr<x1 || x2<st) return 0;
    int mij=st+(dr-st)/2;
    return query(x1, y1, x2, y2, nod*2, st, mij)+query(x1, y1, x2, y2, nod*2+1, mij+1, dr);
}

int main()
{
    in >> n;
    for(int i=1; i<=n; i++)
    {
        in >> puncte[i].x >> puncte[i].y;
        coord_x.push_back(puncte[i].x);
    }
    sort(coord_x.begin(), coord_x.end());
    unic(coord_x);

    coord_y.resize(coord_x.size());
    aint.resize(coord_x.size()*4);

    for(int i=1; i<=n; i++)
    {
        int poz=lower_bound(coord_x.begin(), coord_x.end(), puncte[i].x)-coord_x.begin();
        coord_y[poz].push_back(puncte[i].y);
    }

    for(int i=0; i<coord_x.size(); i++)
    {
        coord_y[i].push_back(-inf);
        sort(coord_y[i].begin(), coord_y[i].end());
        unic(coord_y[i]);

        //out << i << ", " << coord_x[i] << ":  ";
        //for(auto val : coord_y[i]) out << val << " "; out << "\n";
    } //out << "\n";
    build(1, 1, coord_x.size()-1);
    in >> m; //out << "\n";
    while(m--)
    {
        int x1, y1, x2, y2;
        in >> x1 >> y1 >> x2 >> y2;
        int poz_x1=lower_bound(coord_x.begin(), coord_x.end(), x1)-coord_x.begin(), poz_x2=upper_bound(coord_x.begin(), coord_x.end(), x2)-coord_x.begin()-1;
        //out << poz_x1 << " " << poz_x2 << ", " << y1 << " " << y2 << "\n";
        out << query(poz_x1, y1, poz_x2, y2, 1, 1, coord_x.size()-1) << "\n";
    }

    return 0;
}