Cod sursa(job #3168100)

Utilizator emazareMazare Emanuel emazare Data 11 noiembrie 2023 15:56:57
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.24 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

const int Nmax = 16005, INF = 2000000005;
pair<int, int> v[Nmax];
vector<int> aint[4*Nmax];

int n,m,yy1,yy2;

vector<int> interclas(vector<int> v1, vector<int> v2){
    vector<int> v3;
    int i = 0, j = 0, s1 = v1.size(), s2 = v2.size();
    while(i<s1 && j<s2){
        while(i<s1 && (j == s2 || v1[i]<=v2[j])){
            v3.push_back(v1[i]);
            i++;
        }
        while(j<s2 && (i == s1 || v1[i]>v2[j])){
            v3.push_back(v2[j]);
            j++;
        }
    }
    while(i<s1 && (j == s2 || v1[i]<=v2[j])){
        v3.push_back(v1[i]);
        i++;
    }
    while(j<s2 && (i == s1 || v1[i]>v2[j])){
        v3.push_back(v2[j]);
        j++;
    }
    return v3;
}
void build(int node, int st, int dr){
    if(st == dr){
        aint[node].push_back(v[st].second);
        return;
    }
    int mid = (st+dr)/2;
    build(node+node, st, mid);
    build(node+node+1, mid+1, dr);
    aint[node] = interclas(aint[node+node], aint[node+node+1]);
}
int query(int node, int st, int dr, int x, int y){
    if(st == x && dr == y){
        int i0 = lower_bound(aint[node].begin(), aint[node].end(), yy1)-aint[node].begin();
        int i1 = upper_bound(aint[node].begin(), aint[node].end(), yy2)-aint[node].begin();
        return(i1-i0);
    }
    int mid = (st+dr)/2;
    if(y<=mid)
        return query(node+node, st, mid, x, y);
    if(x>mid)
        return query(node+node+1, mid+1, dr, x, y);
    return (query(node+node, st, mid, x, mid)+query(node+node+1, mid+1, dr, mid+1, y));
}

int main()
{
    int i;
    fin >> n;
    for(i=1;i<=n;i++)
        fin >> v[i].first >> v[i].second;
    fin >> m;
    sort(v+1,v+n+1);
    build(1,1,n);
    for(i=1;i<=m;i++){
        int x1,x2,x,y;
        fin >> x1 >> yy1 >> x2 >> yy2;
        pair<int, int> p1,p2;
        p1.first = x1; p1.second = -INF;
        p2.first = x2; p2.second = INF;
        x = lower_bound(v+1,v+n+1,p1)-v;
        y = upper_bound(v+1,v+n+1,p2)-v; y--;
        if(x>y)
            fout << "0\n";
        else
            fout << query(1,1,n,x,y) << '\n';
    }
    return 0;
}