Cod sursa(job #3161496)

Utilizator Robert_MitriRobert Mitri Robert_Mitri Data 27 octombrie 2023 12:18:04
Problema Zoo Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 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 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);

    int i = 0;
    int j = 0;
    int lc = nod*2;
    int rc = nod*2+1;
    a[nod].reserve(a[lc].size()+a[rc].size());
    while(i < a[lc].size() && j < a[rc].size())
    {
        int x = a[lc][i];
        int y = a[rc][j];
        if ( a[lc][i] < a[rc][j] )
            a[nod].push_back(a[lc][i]),i++;
        else
            a[nod].push_back(a[rc][j]),j++;
    }
    while(i<a[lc].size())
        a[nod].push_back(a[lc][i]),i++;
    while(j<a[rc].size())
        a[nod].push_back(a[rc][j]),j++;
}


int query(int nod,int st,int dr,int x,int y,int x2,int y2)
{
    if(x<=st && dr<=x2)
    {
        int mn = lower_bound(a[nod].begin(),a[nod].end(),y) - a[nod].begin();
        int mx = mn;
        int st = mn;
        int dr = a[nod].size()-1;
        while(st<=dr)
        {
            int mid = (st+dr)/2;
            if( a[nod][mid] <= y2)
                mx = max (mx,mid),st=mid+1;
            else
                dr=mid-1;
        }
        return mx-mn+1;
    }
    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';

    }

}