Pagini recente » Cod sursa (job #2676929) | Cod sursa (job #3190653) | Cod sursa (job #1140515) | Cod sursa (job #1961978) | Cod sursa (job #1487997)
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 16000;
const int BUFFSIZE = 1024;
struct point
{
int x, y;
} v[MAX_N];
bool operator <(const point &a, const point &b)
{
return (a.x < b.x) || (a.x == b.x && a.y < b.y);
}
vector <int> tree[2 * MAX_N];
char buff[BUFFSIZE];
int ptr = BUFFSIZE;
inline char getChr()
{
if (ptr == BUFFSIZE)
{
fread(buff, 1, BUFFSIZE, stdin);
ptr = 0;
}
return buff[ptr++];
}
inline int readInt()
{
register int q = 0;
bool sign = 0;
char c;
do
{
c = getChr();
sign |= (c == '-');
} while (!isdigit(c));
do
{
q = (q << 1) + (q << 3) + (c - '0');
c = getChr();
} while (isdigit(c));
return q ^ ((q ^ -q) & -sign);
}
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()
{
freopen("zoo.in", "r", stdin);
freopen("zoo.out", "w", stdout);
int n, q;
int x, y, X, Y;
int lo, hi, mid;
n = readInt();
for (int i = 0; i < n; i++)
v[i] = { readInt(), readInt() };
sort(v, v + n);
for (int i = 0; i < n; i++)
tree[i + n].emplace_back(v[i].y);
for (int i = n - 1; i; i--)
merge(tree[i << 1].begin(), tree[i << 1].end(), tree[(i << 1) | 1].begin(), tree[(i << 1) | 1].end(), back_inserter(tree[i]));
q = readInt();
while (q--)
{
x = readInt();
y = readInt();
X = readInt();
Y = readInt();
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;
printf("%d\n", query(x + n, y, X + n, Y));
}
fclose(stdin);
fclose(stdout);
return 0;
}