Pagini recente » Cod sursa (job #569632) | Cod sursa (job #77339) | Cod sursa (job #47841) | Cod sursa (job #51093) | Cod sursa (job #2456098)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
const int DIM = 16007;
vector <int> arb[DIM * 4];
struct Point
{
int x, y;
int pos;
};
bool cmp(Point a, Point b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
int p = 0;
vector <Point> v;
void build(int pos, int l, int r)
{
if(l == r)
{
while(p < v.size() && v[p].pos == l)
{
arb[pos].push_back(v[p].y);
p++;
}
return ;
}
int mid = (l + r) / 2;
build(pos * 2, l, mid);
build(pos * 2 + 1, mid + 1, r);
int it = 0;
for(auto i : arb[pos * 2])
{
while(it < arb[pos * 2 + 1].size() && arb[pos * 2 + 1][it] <= i)
{
arb[pos].push_back(arb[pos * 2 + 1][it]);
it++;
}
arb[pos].push_back(i);
}
while(it < arb[pos * 2 + 1].size())
{
arb[pos].push_back(arb[pos * 2 + 1][it]);
it++;
}
}
int query(int pos, int l, int r, int x1, int y1, int x2, int y2)
{
if(x1 <= l && r <= x2)
{
int lo = 0;
int hi = arb[pos].size() - 1;
int it1 = 0;
int it2 = 0;
while(lo <= hi)
{
int mid = (lo + hi) / 2;
if(arb[pos][mid] < y1)
{
lo = mid + 1;
}
else
{
hi = mid - 1;
it1 = mid;
}
}
lo = 0;
hi = arb[pos].size() - 1;
while(lo <= hi)
{
int mid = (lo + hi) / 2;
if(arb[pos][mid] > y2)
{
hi = mid - 1;
}
else
{
lo = mid + 1;
it2 = mid;
}
}
if(arb[pos][it1] > y2 || arb[pos][it2] < y1)
return 0;
return it2 - it1 + 1;
}
int mid = (l + r) / 2;
int sum = 0;
if(x1 <= mid)
sum += query(pos * 2, l, mid, x1, y1, x2, y2);
if(x2 > mid)
sum += query(pos * 2 + 1, mid + 1, r, x1, y1, x2, y2);
return sum;
}
main()
{
int n;
fin >> n;
for(int i = 1; i <= n; i++)
{
int x, y;
fin >> x >> y;
v.push_back({x, y, 0});
}
sort(v.begin(), v.end(), cmp);
v[0].pos = 1;
int k = 1;
for(int i = 1; i < v.size(); i++)
{
if(v[i].x != v[i - 1].x)
k++;
v[i].pos = k;
}
build(1, 1, k);
fin >> n;
while(n--)
{
int x1, y1, x2, y2;
fin >> x1 >> y1 >> x2 >> y2;
int l = 0;
int r = v.size() - 1;
int it1 = 0;
int it2 = 0;
while(l <= r)
{
int mid = (l + r) / 2;
if(v[mid].x < x1)
{
l = mid + 1;
}
else
{
r = mid - 1;
it1 = mid;
}
}
l = 0;
r = v.size() - 1;
while(l <= r)
{
int mid = (l + r) / 2;
if(v[mid].x > x2)
{
r = mid - 1;
}
else
{
l = mid + 1;
it2 = mid;
}
}
if(v[it1].x > x2 || v[it2].x < x1)
{
fout << 0 << '\n';
continue;
}
x1 = v[it1].pos;
x2 = v[it2].pos;
int res = query(1, 1, k, x1, y1, x2, y2);
fout << res << '\n';
}
}