Pagini recente » Cod sursa (job #643144) | Cod sursa (job #2443211) | Cod sursa (job #569140) | Cod sursa (job #1591057) | Cod sursa (job #1821606)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin ("zoo.in");
ofstream fout ("zoo.out");
const int N = 65000;
int sol, i, n, xj, m, yj, xs, ys;
vector <int> H[N];
pair <int, int> v[N];
void build(int st,int dr,int po) {
if (st == dr) {
H[po].push_back(0);
return;
}
int mij = (st + dr) >> 1;
if (i <= mij) {
build(st, mij, po << 1);
} else {
build(mij + 1, dr, (po << 1) + 1);
}
H[po].push_back(0);
}
void upd(int st, int dr, int po) {
if (st == dr) {
H[po][0] = v[i].second;
return ;
}
int mij = (st + dr) >> 1;
if (i <= mij) {
upd(st, mij, po << 1);
} else {
upd(mij + 1, dr, (po << 1) + 1);
}
if (i == dr) {
merge(H[po << 1].begin(), H[po << 1].end(), H[(po << 1) + 1].begin(), H[(po << 1) + 1].end(), H[po].begin());
}
}
void query(int st, int dr, int po) {
if (xj <= v[st].first && xs >= v[dr].first) {
vector<int> :: iterator lo = lower_bound(H[po].begin(), H[po].end(), yj);
vector<int> :: iterator hi = upper_bound(H[po].begin(), H[po].end(), ys);
sol += hi - lo;
return;
}
if(st==dr) {
return;
}
int mij = (st + dr) >> 1;
if (xj <= v[mij].first) {
query(st, mij, po << 1);
}
if (xs >= v[mij + 1].first) {
query(mij + 1, dr, (po << 1) + 1);
}
}
int main() {
fin >> n;
for (i = 1; i <= n; ++i) {
fin >> v[i].first >> v[i].second;
}
sort(v + 1, v + n + 1);
for (i = 1; i <= n; ++i) {
build(1, n, 1);
}
for (i = 1; i <= n; ++i) {
upd(1, n, 1);
}
fin >> m;
for (i = 1; i <= m; ++i) {
fin >> xj >> yj >> xs >> ys;
sol = 0;
query(1, n, 1);
fout << sol << "\n";
}
return 0;
}