Cod sursa(job #3161526)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 27 octombrie 2023 13:23:02
Problema Zoo Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define sz 26000

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

pair<int,int> pp[sz + 5];


vector <int> a[sz * 4 + 5];

vector <int> el[sz + 5];

vector <int> vk;
int k;
int k2;

int n;

int q;
void interclass(vector<int>& a,vector<int>& b,vector<int>& c)
{
    int i=0;
    int j=0;
    int sza = a.size();
    int szb = b.size();
    c.clear();
    c.reserve(sza+szb+1);
    while(i<sza && j<szb)
    {
        if(a[i] < b[j])
            c.push_back(a[i]),i++;
        else
            c.push_back(b[j]),j++;
    }
    while(i<sza)
        c.push_back(a[i]),i++;
    while(j<szb)
        c.push_back(a[j]),j++;
}
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        swap(a[nod],el[st]);
        sort(a[nod].begin(),a[nod].end());
        return;
    }
    int mid = (st+dr)/2;
    build(nod*2,st,mid);
    build(nod*2+1,mid+1,dr);
    interclass(a[nod*2],a[nod*2+1],a[nod]);
}



int query(int nod,int st,int dr,int x,int y,int x2,int y2)
{
    if(x<=st && dr<=x2)
        return upper_bound(a[nod].begin(),a[nod].end(),y2) - lower_bound(a[nod].begin(),a[nod].end(),y);
    int mid = (st+dr)/2;
    if(x>mid)
        return query(nod*2+1,mid+1,dr,x,y,x2,y2);
    if(x2<=mid)
        return query(nod*2,st,mid,x,y,x2,y2);
    return query(nod*2,st,mid,x,y,x2,y2) + query(nod*2+1,mid+1,dr,x,y,x2,y2);
}


int main()
{
    fin>>n;
    for(int i =1 ;i<=n;i++)
    {
        fin>>pp[i].first>>pp[i].second;
        vk.push_back(pp[i].first);
    }
    sort(vk.begin(),vk.end());
    vk.resize(unique(vk.begin(),vk.end()) -vk.begin());


    for(int i =1;i<=n;i++){
            pp[i].first = lower_bound(vk.begin(),vk.end(),pp[i].first) - vk.begin() + 1;
            el[pp[i].first].push_back(pp[i].second);
    }
    build(1,1,int(vk.size()));
    fin>>q;

    for(int i=1;i<=q;i++)
    {
        int x,y,x2,y2;

        fin>>x>>y>>x2>>y2;
        int rx = lower_bound(vk.begin(),vk.end(),x) - vk.begin() + 1;
        int rx2 = upper_bound(vk.begin(),vk.end(),x2) - vk.begin();

        if(rx > rx2)
            fout<<0<<'\n';
        else
        fout<<query(1,1,int(vk.size()),rx,y,rx2,y2)<<'\n';

    }

}