Pagini recente » Cod sursa (job #1709629) | Cod sursa (job #2805338) | Cod sursa (job #687124) | Cod sursa (job #3238534) | Cod sursa (job #2966280)
#include <fstream>
#include <algorithm>
#include <map>
using namespace std;
const int NMAX = 16000;
const int QMAX = 100000;
map <int, int> y;
struct query
{
int op;
int x, y;
int y1, y2;
int ind;
} v[NMAX + QMAX * 2 + 1];
int ans[QMAX + 1];
bool cmp(query a, query b)
{
if (a.x != b.x)
return a.x < b.x;
if (a.op == 1 and b.op == 2)
return false;
if (a.op == 2 and b.op == 1)
return true;
return a.op < b.op;
}
int aib[NMAX + QMAX * 2], cnt;
int query(int val)
{
int ans = 0;
while (val)
{
ans += aib[val];
val -= val & -val;
}
return ans;
}
void update(int poz, int val)
{
while (poz <= cnt)
{
aib[poz] += val;
poz += poz & -poz;
}
}
int main()
{
ifstream cin("zoo.in");
ofstream cout("zoo.out");
int n, i;
cin >> n;
int dim = 0;
for (i = 1; i <= n; i++)
{
dim++;
cin >> v[dim].x >> v[dim].y;
y[v[dim].y] = 0;
v[dim].op = 1;
}
int q;
cin >> q;
for (i = 1; i <= q; i++)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
y[y1] = 0;
y[y2] = 0;
dim++;
v[dim].op = 2;
v[dim].x = x1;
v[dim].y1 = y1;
v[dim].y2 = y2;
v[dim].ind = i;
dim++;
v[dim].op = 3;
v[dim].x = x2;
v[dim].y1 = y1;
v[dim].y2 = y2;
v[dim].ind = i;
}
cnt = 0;
for (pair <int, int> aux : y)
y[aux.first] = ++cnt;
sort(v + 1, v + dim + 1, cmp);
for (i = 1; i <= dim; i++)
{
if (v[i].op == 1)
{
v[i].y = y[v[i].y];
update(v[i].y, 1);
}
else
{
v[i].y1 = y[v[i].y1];
v[i].y2 = y[v[i].y2];
if (v[i].op == 2)
{
ans[v[i].ind] -= query(v[i].y2) - query(v[i].y1 - 1);
}
else
{
ans[v[i].ind] += query(v[i].y2) - query(v[i].y1 - 1);
}
}
}
for (i = 1; i <= q; i++)
cout << ans[i] << "\n";
}