Cod sursa(job #3037599)

Utilizator robertanechita1Roberta Nechita robertanechita1 Data 25 martie 2023 22:07:44
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MaxN = 16005;
int n, m;
struct Elem{
    int x, y;
    bool operator < (const Elem A) const{
        if(x == A.x)
            return y < A.y;
        return x < A.x;
    }
}v[MaxN];
vector<int>aint[4 * MaxN];
vector<int>a;

void Build(int nod, int st, int dr){
    if(st == dr){
        aint[nod].push_back(v[st].y);
        return;
    }
    int mid = (st + dr) / 2;
    Build(2 * nod, st, mid);
    Build(2 * nod + 1, mid + 1, dr);
    aint[nod].resize(aint[2 * nod].size() + aint[2 * nod + 1].size());
    merge(aint[2 * nod].begin(), aint[2 * nod].end(), aint[2 * nod + 1].begin(), aint[2 * nod + 1].end(), aint[nod].begin());
}

int Query(int nod, int st, int dr, int p1, int p2, int x, int y){
    int sol1 = 0, sol2 = 0;
    if(p1 <= st && dr <= p2){
        int ans = 0, poz1=0, poz2=0;
        poz1 = lower_bound(aint[nod].begin(), aint[nod].end(), x) - aint[nod].begin();
        poz2 = upper_bound(aint[nod].begin(), aint[nod].end(), y) - aint[nod].begin() ;
        return poz2 - poz1 ;
    }

    int mid = (st + dr) / 2;
    if(p1 <= mid)
        sol1 = Query(2*nod, st, mid, p1, p2, x, y);
    if(p2 > mid)
        sol2 = Query(2*nod+1, mid+1, dr, p1, p2, x, y);
    return sol1 + sol2;
}

int main()
{
    int x1, y1, x2, y2;
    fin >> n ;
    for(int i = 1; i <= n; i++){
        fin >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1);
    for(int i = 1; i <= n; i++)
        a.push_back(v[i].x);
    Build(1, 1, n);
    fin >> m;
    for(int i = 1; i <= m; i++){
        fin >> x1 >> y1 >> x2 >> y2;
        ///caut binar prima val >= cu x1 si ultima val <= x2
        int poz1 = lower_bound(a.begin(), a.end(), x1) - a.begin() + 1;
        int poz2 = upper_bound(a.begin(), a.end(), x2) - a.begin();
        ///poz2 = poz primei val > x2 => poz2++

        ///acum stiu pe ce linii caut
        if(poz1 <= n && poz2 > 0)
            fout << Query(1, 1, n, poz1, poz2, y1, y2) << "\n";
        else
            fout << "0\n";
    }
    return 0;
}