Cod sursa(job #3163068)

Utilizator Cazacu2006RazvanRazvan Cazacu Cazacu2006Razvan Data 30 octombrie 2023 14:45:01
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.67 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
int n,v[500001],k,k2,sol,m;
vector <int> A[500001];
struct numar
{
    int x,y;
}a[16001];
struct numar2
{
    int x1,y1,x2,y2;
}b[100001];
int cb(int x)
{
    int st=0,dr=k-1,mid=0;
    while(st<=dr)
    {
        mid=(st+dr)/2;
        if(x>v[mid])
            st=mid+1;
        else if(x<v[mid])
            dr=mid-1;
        else
        {
            return mid;
        }
    }
}
void build(int nod,int st,int dr)
{
  for(int i=st;i<=dr;i++)
    A[nod].push_back(a[i].y);
  sort(A[nod].begin(),A[nod].end());
  if(st<dr)
  {
      int mid=(st+dr)/2;
      build(nod*2,st,mid);
      build(nod*2+1,mid+1,dr);
  }

}
int cu(int nod,int x)
{
    int st=0,dr=A[nod].size()-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(A[nod][mid]<=x)
        {
            st=mid+1;

        }
        else
            dr=mid-1;
    }
    return dr;

}
int cp(int nod,int x)
{
    int st=0,dr=A[nod].size()-1;
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(A[nod][mid]>=x)
        {
            dr=mid-1;

        }
        else
        {
            st=mid+1;

        }

    }
    return st;

}
void query(int nod,int st,int dr,int x1,int x2,int y1,int y2)
{

    if(x1<=a[st].x && a[dr].x<=x2)
    {

        sol+=(cu(nod,y2)-cp(nod,y1)+1);

    }
    else if(st<dr)
    {
        int mid=(st+dr)/2;
        if(x1<=a[mid].x)
            query(nod*2,st,mid,x1,x2,y1,y2);
        if(x2>=a[mid+1].x)
            query(nod*2+1,mid+1,dr,x1,x2,y1,y2);
    }
}
int cmp(numar a,numar b)
{
    return a.x<b.x;
}
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i].x>>a[i].y;
        v[k++]=a[i].x;
        v[k++]=a[i].y;
    }
     fin>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>b[i].x1>>b[i].y1>>b[i].x2>>b[i].y2;
        v[k++]=b[i].x1;
        v[k++]=b[i].y1;
        v[k++]=b[i].x2;
        v[k++]=b[i].y2;
    }
    sort(v,v+k);

    for(int i=1;i<=k;i++)
    {
        if(v[i]!=v[k2])
        {

            v[++k2]=v[i];

        }
    }

    k=k2+1;


    for(int i=1;i<=n;i++)
    {
        a[i].x=cb(a[i].x);
        a[i].y=cb(a[i].y);
    }
    for(int i=1;i<=m;i++)
    {
        b[i].x1=cb(b[i].x1);
        b[i].y1=cb(b[i].y1);
        b[i].x2=cb(b[i].x2);
        b[i].y2=cb(b[i].y2);
    }

    sort(a+1,a+n+1,cmp);

    build(1,1,n);
    for(int i=1;i<=m;i++)
    {
        sol=0;
        query(1,1,n,b[i].x1,b[i].x2,b[i].y1,b[i].y2);
        fout<<sol<<"\n";
    }

    return 0;
}