Cod sursa(job #3161500)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 27 octombrie 2023 12:29:23
Problema Zoo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define sz 16000

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];

int vk[sz + 5];
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.reserve(sza+szb);
    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)
    {
        a[nod] = el[st];
        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 cb(int val)
{
    int st =1;
    int dr = k2;
    while(st<=dr)
    {
        int mid = (st+dr)/2;
        if ( val < vk[mid])
            dr=mid-1;
        else if ( val > vk[mid])
            st=mid+1;
        else
            return mid;
    }
}

int main()
{
    fin>>n;
    for(int i =1 ;i<=n;i++)
    {
        fin>>pp[i].first>>pp[i].second;
        vk[++k] = pp[i].first;
    }
    sort(vk+1,vk+k+1);
    k2=1;
    for(int i = 2; i<=k;i++)
        if(vk[i]!=vk[i-1])
            vk[++k2]=vk[i];
    for(int i =1;i<=n;i++)
        el[cb(pp[i].first)].push_back(pp[i].second);
    build(1,1,k2);
    fin>>q;
    for(int i=1;i<=q;i++)
    {
        int x,y,x2,y2;
        int rx = k2+1,rx2 = -1;
        fin>>x>>y>>x2>>y2;
        int st = 1;
        int dr = k2;
        while(st<=dr)
        {
            int mid = (st+dr)/2;
            if(vk[mid] < x)
                st=mid+1;
            else
                dr=mid-1,rx=min(rx,mid);
        }
        st=1;
        dr=k2;
        while(st<=dr)
        {
            int mid = (st+dr)/2;
            if(vk[mid] > x2)
                dr=mid-1;
            else
                st=mid+1,rx2=max(rx2,mid);
        }
        if(rx2 < rx){
            fout<<0<<'\n';
            continue;
        }
        fout<<query(1,1,k2,rx,y,rx2,y2)<<'\n';

    }

}