Pagini recente » Cod sursa (job #926804) | Cod sursa (job #1918236) | Cod sursa (job #2902934) | Cod sursa (job #1626585) | Cod sursa (job #742090)
Cod sursa(job #742090)
#include<fstream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
int n,Q,xmin,ymin,xmax,ymax,sol;
struct Punct{int x,y;};
Punct P[17000];
struct Nod{vector <int> Y;};
Nod Aint[33000];
inline bool SortareX(Punct A,Punct B)
{
return A.x<B.x;
}
inline void Construire_ArboreIntervale(int nod,int st,int dr)
{
if(st==dr)
{
Aint[nod].Y.push_back(P[st].y);
return;
}
int mij=(st+dr)/2,fiu=2*nod;
Construire_ArboreIntervale(fiu,st,mij);
Construire_ArboreIntervale(fiu+1,mij+1,dr);
Aint[nod].Y.resize(dr-st+1);
//merge(Aint[fiu].Y.begin(),Aint[fiu].Y.end(),Aint[fiu+1].Y.begin(),Aint[fiu+1].Y.end(),Aint[nod].Y.begin());
int i,j,k;
i=j=k=0;
while(j<Aint[fiu].Y.size() && k<Aint[fiu+1].Y.size())
{
if(Aint[fiu].Y[j]<Aint[fiu+1].Y[k])
{
Aint[nod].Y[i]=Aint[fiu].Y[j];
j++;
}
else
{
Aint[nod].Y[i]=Aint[fiu+1].Y[k];
k++;
}
i++;
}
while(j<Aint[fiu].Y.size())
{
Aint[nod].Y[i]=Aint[fiu].Y[j];
j++;
i++;
}
while(k<Aint[fiu+1].Y.size())
{
Aint[nod].Y[i]=Aint[fiu+1].Y[k];
k++;
i++;
}
}
inline void Query(int nod,int st,int dr)
{
if(xmin<=P[st].x && P[dr].x<=xmax)
{
int poz1,poz2;
poz1=lower_bound(Aint[nod].Y.begin(),Aint[nod].Y.end(),ymin)-Aint[nod].Y.begin();
poz2=upper_bound(Aint[nod].Y.begin(),Aint[nod].Y.end(),ymax)-Aint[nod].Y.begin();
sol+=(poz2-poz1);
return;
}
int mij=(st+dr)/2,fiu=2*nod;
if(xmin<=P[mij].x)
Query(fiu,st,mij);
if(P[mij+1].x<=xmax)
Query(fiu+1,mij+1,dr);
}
int main()
{
int i;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
fin>>n;
for(i=1;i<=n;i++)
fin>>P[i].x>>P[i].y;
sort(P+1,P+n+1,SortareX);
Construire_ArboreIntervale(1,1,n);
fin>>Q;
for(i=1;i<=Q;i++)
{
fin>>xmin>>ymin>>xmax>>ymax;
sol=0;
Query(1,1,n);
fout<<sol<<"\n";
}
fin.close();
fout.close();
return 0;
}