Pagini recente » Cod sursa (job #406845) | Cod sursa (job #607811) | Cod sursa (job #1754) | Cod sursa (job #315736) | Cod sursa (job #615751)
Cod sursa(job #615751)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const char InFile[]="zoo.in";
const char OutFile[]="zoo.out";
const int MaxN=16111;
const int AINT_SIZE=MaxN<<2;
const int BUFFER_SIZE=5*1024*1024;
ifstream fin(InFile);
ofstream fout(OutFile);
struct point
{
point(int x=0, int y=0):x(x),y(y){}
int x,y;
};
struct cmp_point_x
{
inline bool operator() (const point &a, const point &b)
{
return a.x<b.x;
}
};
struct aint_node
{
vector<int> y;
};
unsigned int ind,ind1,ind2;
int N,M,sol,xmin,ymin,xmax,ymax,pst,pdr;
aint_node aint[AINT_SIZE];
point p[MaxN];
char buffer[BUFFER_SIZE];
char *ptr=(buffer+1);
inline int number()
{
int sol=0;
while(!('0'<=*ptr && *ptr<='9'))
{
++ptr;
}
int sign=1;
if(*(ptr-1)=='-')
{
sign=-1;
}
while('0'<=*ptr && *ptr<='9')
{
sol*=10;
sol+=*ptr-'0';
++ptr;
}
return sign*sol;
}
inline void cauta(const int &nod)
{
int p=0,u=aint[nod].y.size()-1;
while(p<=u)
{
int m=p+((u-p)>>1);
if(aint[nod].y[m]>=ymin)
{
u=m-1;
}
else
{
p=m+1;
}
}
int st=p;
p=0,u=aint[nod].y.size()-1;
while(p<=u)
{
int m=p+((u-p)>>1);
if(aint[nod].y[m]<=ymax)
{
p=m+1;
}
else
{
u=m-1;
}
}
int dr=u;
sol+=dr-st+1;
}
void init(int nod, int st, int dr)
{
if(st==dr)
{
aint[nod].y.push_back(p[st].y);
return;
}
int l=nod<<1;
int mid=st+((dr-st)>>1);
init(l,st,mid);
init(l+1,mid+1,dr);
aint[nod].y.resize(dr-st+1);
ind=0;
ind1=0;
ind2=0;
while(ind1<aint[l].y.size() && ind2<aint[l+1].y.size())
{
if(aint[l].y[ind1]<aint[l+1].y[ind2])
{
aint[nod].y[ind]=aint[l].y[ind1];
++ind1;
}
else
{
aint[nod].y[ind]=aint[l+1].y[ind2];
++ind2;
}
++ind;
}
while(ind1<aint[l].y.size())
{
aint[nod].y[ind]=aint[l].y[ind1];
++ind1;
++ind;
}
while(ind2<aint[l+1].y.size())
{
aint[nod].y[ind]=aint[l+1].y[ind2];
++ind2;
++ind;
}
}
void query(int nod, int st, int dr)
{
if(pst<=st && dr<=pdr)
{
cauta(nod);
return;
}
int mid=st+((dr-st)>>1);
nod<<=1;
if(pst<=mid)
{
query(nod,st,mid);
}
if(mid<pdr)
{
query(nod+1,mid+1,dr);
}
}
int main()
{
fin.rdbuf()->sgetn( ptr, BUFFER_SIZE-1 );
fin.close();
N=number();
for(register int i=1;i<=N;++i)
{
p[i].x=number();
p[i].y=number();
}
sort(p+1,p+1+N,cmp_point_x());
init(1,1,N);
M=number();
for(register int i=1;i<=M;++i)
{
sol=0;
xmin=number(); ymin=number(); xmax=number(); ymax=number();
int p=1,u=N;
while(p<=u)
{
int m=p+((u-p)>>1);
if(::p[m].x>=xmin)
{
u=m-1;
}
else
{
p=m+1;
}
}
pst=p;
p=1;u=N;
while(p<=u)
{
int m=p+((u-p)>>1);
if(::p[m].x<=xmax)
{
p=m+1;
}
else
{
u=m-1;
}
}
pdr=u;
if(1<=pst && pst<=pdr && pdr<=N)
{
query(1,1,N);
}
fout<<sol<<"\n";
}
fout.close();
return 0;
}