Pagini recente » Cod sursa (job #2981504) | Cod sursa (job #163302) | Cod sursa (job #1695737) | Cod sursa (job #2733037) | Cod sursa (job #1487988)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 16000;
struct point
{
int x, y;
} v[MAX_N];
vector <int> tree[2 * MAX_N];
bool cmp(const point &a, const point &b)
{
return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}
inline int query(int l, const int &y, int r, const int &Y)
{
int ans = 0;
while (l < r)
{
if (l & 1)
{
ans += upper_bound(tree[l].begin(), tree[l].end(), Y) - lower_bound(tree[l].begin(), tree[l].end(), y);
l++;
}
if (r & 1)
{
r--;
ans += upper_bound(tree[r].begin(), tree[r].end(), Y) - lower_bound(tree[r].begin(), tree[r].end(), y);
}
l >>= 1;
r >>= 1;
}
return ans;
}
int main()
{
ifstream in("zoo.in");
ofstream out("zoo.out");
int n, q;
int x, y, X, Y;
int lo, hi, mid;
in >> n;
for (int i = 0; i < n; i++)
in >> v[i].x >> v[i].y;
sort(v, v + n, cmp);
for (int i = 0; i < n; i++)
tree[i + n].emplace_back(v[i].y);
for (int i = n - 1; i; i--)
merge(tree[2 * i].begin(), tree[2 * i].end(), tree[2 * i + 1].begin(), tree[2 * i + 1].end(), back_inserter(tree[i]));
in >> q;
while (q--)
{
in >> x >> y >> X >> Y;
lo = -1;
hi = n;
while (hi - lo > 1)
{
mid = (lo + hi) >> 1;
if (v[mid].x >= x)
hi = mid;
else
lo = mid;
}
x = hi;
lo = -1;
hi = n;
while (hi - lo > 1)
{
mid = (lo + hi) >> 1;
if (v[mid].x <= X)
lo = mid;
else
hi = mid;
}
X = lo + 1;
out << query(x + n, y, X + n, Y) << '\n';
}
in.close();
out.close();
return 0;
}