Pagini recente » Cod sursa (job #1214159) | Cod sursa (job #564652) | Cod sursa (job #1879066) | Cod sursa (job #841424) | Cod sursa (job #3162589)
#include <fstream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
ifstream fin ("zoo.in");
ofstream fout ("zoo.out");
int x[16001],y[16001],x1[16001],y1[16001],x2[16001],y2[16001];
int m,n,xp1,xp2,yp1,yp2,i,j,nr,sol;
vector <int> aint[464001],v,p[116001];
unordered_map <int,int> fr;
void f (int nod)
{
int n=aint[2*nod].size ()-1;
int m=aint[2*nod+1].size ()-1;
int i=1,j=1;
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=1,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=1,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]=p[st];
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 (st==dr)
sol+=cb2 (aint[nod],yp2)-cb1 (aint[nod],yp1)+1;
else
{
int mij=(st+dr)/2;
if (xp1<=mij)
query (2*nod,st,mij);
if (xp2>mij)
query (2*nod+1,mij+1,dr);
}
}
int main ()
{
fin>>n;
for (i=1; i<=n; i++)
{
fin>>x[i]>>y[i];
v.push_back (x[i]);
}
fin>>m;
for (i=1; i<=m; i++)
{
fin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
v.push_back (x1[i]);
v.push_back (x2[i]);
}
sort (v.begin (),v.end ());
nr=0;
fr[v[0]]=++nr;
for (i=1; i<v.size (); i++)
{
if (v[i]!=v[i-1])
fr[v[i]]=++nr;
}
for (i=1; i<=nr; i++)
p[i].push_back (0);
for (i=1; i<=n; i++)
{
x[i]=fr[x[i]];
p[x[i]].push_back (y[i]);
}
for (i=1; i<=m; i++)
{
x1[i]=fr[x1[i]];
x2[i]=fr[x2[i]];
}
build (1,1,nr);
for (i=1; i<=m; i++)
{
sol=0;
xp1=x1[i];
yp1=y1[i];
xp2=x2[i];
yp2=y2[i];
query (1,1,nr);
fout<<sol<<"\n";
}
return 0;
}