Pagini recente » Cod sursa (job #2209758) | Cod sursa (job #2044601) | Cod sursa (job #491859) | Cod sursa (job #2269578) | Cod sursa (job #2825874)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 16e3 + 5;
struct p {
int x, y;
bool operator<(const p& P) const {
return x < P.x;
}
};
int n;
p coord[N];
vector<int> aib[N];
int zeros(int x) {
return x ^ (x & (x - 1));
}
void update(int poz, int val) {
while (poz <= n) {
aib[poz].push_back(val);
poz += zeros(poz);
}
}
int query(int poz, int y1, int y2) {
int rez = 0;
while (poz > 0) {
int sus = upper_bound(aib[poz].begin(), aib[poz].end(), y2) - aib[poz].begin();
int jos = lower_bound(aib[poz].begin(), aib[poz].end(), y1) - aib[poz].begin();
rez += sus - jos;
poz -= zeros(poz);
}
return rez;
}
int main() {
ifstream cin("zoo.in");
ofstream cout("zoo.out");
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> coord[i].x >> coord[i].y;
//normalizez
sort(coord + 1, coord + n + 1);
//construiesc aib
for (int i = 1; i <= n; ++i)
update(i, coord[i].y);
for (int i = 1; i <= n; ++i)
sort(aib[i].begin(), aib[i].end());
int q;
cin >> q;
while (q--) {
p c1, c2;
cin >> c1.x >> c1.y >> c2.x >> c2.y;
int poz1 = lower_bound(coord + 1, coord + n + 1, c1) - coord;
if (poz1 > 0) --poz1;
int poz2 = upper_bound(coord + 1, coord + n + 1, c2) - coord;
if (poz2 > 0) --poz2;
cout << query(poz2, c1.y, c2.y) - query(poz1, c1.y, c2.y) << "\n";
}
cin.close();
cout.close();
return 0;
}