Cod sursa(job #3162735)

Utilizator Bianca2507Negret Bianca Bianca2507 Data 29 octombrie 2023 19:20:34
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.95 kb
#include <fstream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
ifstream cin("zoo.in");
ofstream cout("zoo.out");

struct coord_dreptunghi
{
    int x1,y1,x2,y2;
} d[100002];

pair<int,int>coord[16002];
vector<int>aint[5*100001];
int p[5*100000+5],nr,n,m,sol;

int cb(int a)
{
    int st=0;
    int dr=nr-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(p[mid]==a)
            return mid;
        else if(p[mid]>a)
            dr=mid-1;
        else
            st=mid+1;
    }
}
int cb_primul(int a,int nod)
{
    int st=0;
    int dr=aint[nod].size()-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(aint[nod][mid]>=a)
            dr=mid-1;
        else
            st=mid+1;
    }
    return st;
}

int cb_ultim(int a,int nod)
{
    int st=0;
    int dr=aint[nod].size()-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(aint[nod][mid]<=a)
            st=mid+1;
        else
            dr=mid-1;
    }
    return dr;
}

void build(int nod,int st,int dr)
{
    for(int i=st; i<=dr; i++)
        aint[nod].push_back(coord[i].second);

    sort(aint[nod].begin(), aint[nod].end());

    if(st<dr)
    {
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);

    }
}
void query(int nod,int st,int dr,int nr_drept)
{
    if(st>dr)
        return ;

    if(d[nr_drept].x1<=coord[st].first&&coord[dr].first<=d[nr_drept].x2)
        sol+=cb_ultim(d[nr_drept].y2,nod)-cb_primul(d[nr_drept].y1,nod)+1;
    else
    {
        if(st==dr)
            return;

        int mid=(st+dr)/2;
        if(d[nr_drept].x1<=coord[mid].first)
            query(2*nod,st,mid,nr_drept);
        if(d[nr_drept].x2>=coord[mid+1].first)
            query(2*nod+1,mid+1,dr,nr_drept);
    }
}
int main()
{
    cin>>n;
    ///normalizare
    for(int i=1; i<=n; i++)
    {
        cin>>coord[i].first>>coord[i].second;
        p[nr++]=coord[i].first;
        p[nr++]=coord[i].second;
    }
    cin>>m;
    for(int i=1; i<=m; i++)
    {
        cin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2;
        p[nr++]=d[i].x1;
        p[nr++]=d[i].y1;
        p[nr++]=d[i].x2;
        p[nr++]=d[i].y2;
    }
    sort(p,p+nr);
    int aux=0;
    for(int i=1; i<nr; i++)
        if(p[aux]!=p[i])
        {
            p[++aux]=p[i];
        }
    nr=aux+1;
    for(int i=1; i<=n; i++)
    {
        coord[i].first=cb(coord[i].first);
        coord[i].second=cb(coord[i].second);
    }
    for(int i=1; i<=m; i++)
    {
        d[i].x1=cb(d[i].x1);
        d[i].y1=cb(d[i].y1);
        d[i].x2=cb(d[i].x2);
        d[i].y2=cb(d[i].y2);
    }
    sort(coord+1,coord+n+1);
    build(1,1,n);///construim arborele de intervale in care adaugam fiecare punct in intervalele din care face parte
    for(int i=1; i<=m; i++)
    {
        sol=0;
        query(1,1,n,i);
        cout<<sol<<'\n';
    }
    return 0;
}