Cod sursa(job #3330760)

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

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

int n, m;
vector<int> coord_x;
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-1];
        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());
}

int query(int x1, int y1, int x2, int y2, int nod, int st, int dr)
{
    if(x1<=st && dr<=x2)
    {
        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++)
    {
        sort(coord_y[i].begin(), coord_y[i].end());
    }
    build(1, 1, coord_x.size());
    in >> m;
    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()+1, poz_x2=upper_bound(coord_x.begin(), coord_x.end(), x2)-coord_x.begin();
        out << query(poz_x1, y1, poz_x2, y2, 1, 1, coord_x.size()) << "\n";
    }

    return 0;
}