Pagini recente » Cod sursa (job #479461) | Cod sursa (job #2322810) | Cod sursa (job #1627113) | Cod sursa (job #2750581) | Cod sursa (job #949309)
Cod sursa(job #949309)
#include<fstream>
#include<vector>
#include<algorithm>
#define punct pair<int,int>
#define x first
#define y second
#define pb push_back
#define lb lower_bound
#define dreptunghi pair<pair<int,int>,pair<int,int> >
#define x1 first.first
#define x2 first.second
#define y1 second.first
#define y2 second.second
#define b begin
#define e end
using namespace std;
ifstream f("zoo.in");
ofstream g("zoo.out");
int i,m,n;
punct p[16010];
dreptunghi d;
vector<int>v[50010];
void interclasare(int nod)
{
v[nod].resize(v[nod<<1].size()+v[(nod<<1)+1].size());
int i=0,j=0,k=0;
while(i<v[nod<<1].size()&&j<v[(nod<<1)+1].size())
{
if(v[nod<<1][i]<v[(nod<<1)+1][j])
{
v[nod][k]=v[nod<<1][i];
++k;
++i;
}
else
{
v[nod][k]=v[(nod<<1)+1][j];
++k;
++j;
}
}
while(i<v[nod<<1].size())
{
v[nod][k]=v[nod<<1][i];
++k;
++i;
}
while(j<v[(nod<<1)+1].size())
{
v[nod][k]=v[(nod<<1)+1][j];
++k;
++j;
}
}
void update(int nod,int li,int ls)
{
if(li==ls)
{
v[nod].pb(p[li].y);
return;
}
int mij=(li+ls)>>1;
update(nod<<1,li,mij);
update((nod<<1)+1,mij+1,ls);
interclasare(nod);
}
int query(int nod,int li,int ls)
{
if(d.x1<=p[li].x&&d.x2>=p[ls].x)
{
return lb(v[nod].b(),v[nod].e(),d.y2+1)-lb(v[nod].b(),v[nod].e(),d.y1);
}
if(li==ls)
return 0;
int mij=(li+ls)>>1,sol=0;
if(d.x1<=p[mij].x)
sol+=query(nod<<1,li,mij);
if(d.x2>=p[mij+1].x)
sol+=query((nod<<1)+1,mij+1,ls);
return sol;
}
int main()
{
f>>n;
for(i=1;i<=n;++i)
f>>p[i].x>>p[i].y;
sort(p+1,p+n+1);
update(1,1,n);
for(f>>m;m;--m)
{
f>>d.x1>>d.y1>>d.x2>>d.y2;
d.x1=max(d.x1,p[1].x);
d.x2=min(d.x2,p[n].x);
g<<query(1,1,n)<<'\n';
}
return 0;
}