Cod sursa(job #2485630)

Utilizator alexradu04Radu Alexandru alexradu04 Data 1 noiembrie 2019 20:18:34
Problema Zoo Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> a,aint[48005];
struct Gigel
{
    int x,y;
};
struct Gigel1
{
    int x1,x2,y1,y2;
}query[48005];
Gigel v[48005];
void Build (int nod,int st,int dr)
{
  if(st==dr)
  {
    aint[nod].push_back(v[dr].y);
    return;
  }
  int mid=st-(st-dr)/2;
  Build(2*nod,st,mid);
  Build(2*nod+1,mid+1,dr);
  aint[nod].resize(aint[2*nod].size()+aint[2*nod+1].size());
  merge(aint[2*nod].begin(),aint[2*nod].end(),aint[2*nod+1].begin(),aint[2*nod+1].end(),aint[nod].begin());
}
int Query(int nod,int st,int dr,int p1,int p2,int x,int y)
{
    if(p1<=st&&dr<=p2)
    {
        return upper_bound(aint[nod].begin(),aint[nod].end(),y)-lower_bound(aint[nod].begin(),aint[nod].end(),x);
    }
    int mid=st-(st-dr)/2,sol1=0,sol2=0;
    if(p1<=mid)
    {
        sol1=Query(2*nod,st,mid,p1,p2,x,y);
    }
    if(p2>mid)
    {
        sol2=Query(2*nod+1,mid+1,dr,p1,p2,x,y);
    }
    return sol1+sol2;
}
bool cmp (Gigel a,Gigel b)
{
  if(a.x==b.x)
    return a.y<b.y;
  return a.x<b.x;
}
int main()
{
    freopen("zoo.in","r",stdin);
    freopen("zoo.out","w",stdout);
  int n,m;
  scanf("%d",&n);
  for(int i=1; i<=n; ++i)
  {
    scanf("%d %d",&v[i].x,&v[i].y);

  }
  sort(v+1,v+n+1,cmp);
  for(int i=1;i<=n;++i)
    a.push_back(v[i].x);
  Build(1,1,n);
  scanf("%d",&m);
  for(int i=1; i<=m; ++i)
  {
    scanf("%d %d %d %d",&query[i].x1,&query[i].y1,&query[i].x2,&query[i].y2);
  }
  for(int i=1; i<=m; ++i)
  {
    int ind1=lower_bound(a.begin(),a.end(),query[i].x1)-a.begin();
    int ind2=upper_bound(a.begin(),a.end(),query[i].x2)-a.begin()-1;
    if(ind1<n&&ind2>=0)
        printf("%d\n",Query(1,1,n,ind1+1,ind2+1,query[i].y1,query[i].y2));
    else
        printf("0\n");
  }
  return 0;
}