Cod sursa(job #3162743)

Utilizator Bianca2507Negret Bianca Bianca2507 Data 29 octombrie 2023 19:33:39
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.35 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 interclaseaza(int nod)
{
    int i=0,j=0;
    int l1=aint[2*nod].size()-1;
    int l2=aint[2*nod+1].size()-1;
    while(i<=l1&&j<=l2)
    {
        if(aint[2*nod][i]<=aint[2*nod+1][j])
            aint[nod].push_back(aint[2*nod][i++]);
        else
             aint[nod].push_back(aint[2*nod+1][j++]);
    }
    for(;i<=l1;i++)
        aint[nod].push_back(aint[2*nod][i]);
    for(;j<=l2;j++)
    aint[nod].push_back(aint[2*nod+1][j]);
}
void build(int nod,int st,int dr)
{
    if(st==dr)
    {
        aint[nod].push_back(coord[st].second);
    }
    else
        if(st<dr)
    {
        int mid=(st+dr)/2;
        build(2*nod,st,mid);
        build(2*nod+1,mid+1,dr);
        interclaseaza(nod);
    }
}
void query(int nod,int st,int dr,int nr_drept)
{

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