Pagini recente » Cod sursa (job #526529) | Cod sursa (job #1540749) | Cod sursa (job #2298246) | Cod sursa (job #1737587) | Cod sursa (job #1152889)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("zoo.in");
ofstream fout ("zoo.out");
struct point
{
int x,y;
}v[16001];
vector <int> V[16001*4];
int n,m,ans,l,r,x1,x2,yy1,y2;
bool cmp (point a, point b)
{
return a.x < b.x;
}
void create_arb (int node, int left, int right)
{
if (left == right)
{
V[node].push_back (v[left].y);
return;
}
int mid = (left + right)/2;
create_arb (node<<1,left,mid);
create_arb ((node<<1)+1,mid+1,right);
V[node].resize (right-left+1);
merge (V[node<<1].begin(),V[node<<1].end(),V[(node<<1)+1].begin(),V[(node<<1)+1].end(),V[node].begin());
}
void query (int node, int left, int right)
{
if (l <= left && right <= r)
{
vector<int>::iterator lo = lower_bound (V[node].begin(),V[node].end(),yy1);
vector<int>::iterator hi = upper_bound (V[node].begin(),V[node].end(),y2);
ans += hi - lo;
return;
}
int mid = (left + right)/2;
if (l <= mid)
query (node<<1,left,mid);
if (r > mid)
query ((node<<1)+1,mid+1,right);
}
int main()
{
fin>>n;
for (int i=1; i<=n; ++i)
{
fin>>v[i].x>>v[i].y;
}
sort (v+1,v+n+1,cmp);
create_arb(1,1,n);
fin>>m;
for (int i=1; i<=m; ++i)
{
fin>>x1>>yy1>>x2>>y2;
int lo = 0, hi = n+1;
while (hi - lo > 1)
{
int mid = (lo + hi)/2;
if (x1 <= v[mid].x)
hi = mid;
else lo = mid;
}
l = hi;
lo = 0, hi = n+1;
while (hi - lo > 1)
{
int mid = (lo + hi)/2;
if (x2 >= v[mid].x)
lo = mid;
else hi = mid;
}
r = lo;
ans = 0;
query(1,1,n);
fout<<ans<<"\n";
}
}