Pagini recente » Cod sursa (job #1851738) | Cod sursa (job #184740) | Cod sursa (job #2816951) | Cod sursa (job #1514804) | Cod sursa (job #3162669)
#include <fstream>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;
ifstream fin ("zoo.in");
ofstream fout ("zoo.out");
int x1[100001],y1[100001],x2[100001],y2[100001];
int m,n,xp1,xp2,yp1,yp2,i,j,nr,sol;
vector <int> aint[64001];
pair <int,int> v[16001];
void f (int nod)
{
int n=aint[2*nod].size ()-1;
int m=aint[2*nod+1].size ()-1;
int i=0,j=0;
while (i<=n&&j<=m)
{
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++]);
}
while (i<=n)
aint[nod].push_back (aint[2*nod][i++]);
while (j<=m)
aint[nod].push_back (aint[2*nod+1][j++]);
}
int cb1 (vector <int> &v,int x)
{
int st=0,dr=v.size ()-1,mij;
while (st<=dr)
{
mij=(st+dr)/2;
if (v[mij]>=x)
dr=mij-1;
else
st=mij+1;
}
return st;
}
int cb2 (vector <int> &v,int x)
{
int st=0,dr=v.size ()-1,mij;
while (st<=dr)
{
mij=(st+dr)/2;
if (v[mij]<=x)
st=mij+1;
else
dr=mij-1;
}
return dr;
}
void build (int nod,int st,int dr)
{
if (st==dr)
aint[nod].push_back (v[st].s);
else
{
int mij=(st+dr)/2;
build (2*nod,st,mij);
build (2*nod+1,mij+1,dr);
f (nod);
}
}
void query (int nod,int st,int dr)
{
if (v[st].f>=xp1&&v[dr].f<=xp2)
sol+=cb2 (aint[nod],yp2)-cb1 (aint[nod],yp1)+1;
else
{
if (st==dr)
return ;
int mij=(st+dr)/2;
if (xp1<=v[mij].f)
query (2*nod,st,mij);
if (xp2>=v[mij].f)
query (2*nod+1,mij+1,dr);
}
}
int main ()
{
fin>>n;
for (i=1; i<=n; i++)
fin>>v[i].f>>v[i].s;
sort (v+1,v+n+1);
build (1,1,n);
fin>>m;
for (i=1; i<=m; i++)
fin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
for (i=1; i<=m; i++)
{
sol=0;
xp1=x1[i];
yp1=y1[i];
xp2=x2[i];
yp2=y2[i];
query (1,1,n);
fout<<sol<<"\n";
}
return 0;
}