Pagini recente » Cod sursa (job #2266986) | Cod sursa (job #371804) | Cod sursa (job #1194012) | Cod sursa (job #1439801) | Cod sursa (job #2966293)
#include <fstream>
#include <algorithm>
using namespace std;
const int NMAX = 16000;
const int QMAX = 100000;
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 + b.op == 3)
return a.op > b.op;
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;
}
}
pair <int, int> val[NMAX + 2 * QMAX + 1];
int siz;
int norm(int x)
{
int med, st = 1, dr = siz;
while (st <= dr)
{
med = ((st + dr) >> 1);
if (val[med].first < x)
st = med + 1;
else if (val[med].first > x)
dr = med - 1;
else
return val[med].second;
}
}
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;
v[dim].op = 1;
val[++siz].first = v[dim].y;
}
int q;
cin >> q;
for (i = 1; i <= q; i++)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
val[++siz].first = y1;
val[++siz].first = y2;
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 = 1;
sort(val + 1, val + siz + 1);
for (i = 1; i + 1 <= siz; i++)
{
val[i].second = cnt;
if (val[i].first != val[i + 1].first)
{
cnt++;
}
}
val[i].second = cnt;
cnt++;
/*for (i = 1; i <= siz; i++)
cout << val[i].first << " ";
cout << "\n";
for (i = 1; i <= siz; i++)
cout << val[i].second << " ";
//return 0;*/
sort(v + 1, v + dim + 1, cmp);
for (i = 1; i <= dim; i++)
{
if (v[i].op == 1)
{
v[i].y = norm(v[i].y);
update(v[i].y, 1);
}
else
{
v[i].y1 = norm(v[i].y1);
v[i].y2 = norm(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";
}