Pagini recente » Cod sursa (job #294233) | Cod sursa (job #2786973) | Cod sursa (job #1102105) | Cod sursa (job #277158) | Cod sursa (job #749952)
Cod sursa(job #749952)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream in("zoo.in");
ofstream out("zoo.out");
struct pct {
int x, y;
};
const int N = 16010;
int n, m, x1, val1, x2, val2, x, y, rez;
pct v[N];
vector<int> aint[3*N];
inline bool cmp(const pct &a, const pct &b) {
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
inline int min(const int &a, const int &b) {
return a < b ? a : b;
}
inline int load(const int &nod) {
vector<int>::iterator it1 = aint[2*nod].begin(), it2 = aint[2*nod + 1].begin();
aint[nod].clear();
for(int i = 1; i<=aint[2*nod].size() + aint[2*nod + 1].size(); ++i) {
if(it1 == aint[2*nod].end()) {
aint[nod].push_back(*it2);
++it2;
continue;
}
if(it2 == aint[2*nod + 1].end()) {
aint[nod].push_back(*it1);
++it1;
continue;
}
aint[nod].push_back(min(*it1, *it2));
if((*it1) < (*it2))
++it1;
else
++it2;
}
}
void build(const int &nod, const int &pozx, const int &pozy) {
if(pozx == pozy) {
aint[nod].push_back(v[pozx].y);
return;
}
int mid = (pozx + pozy)>>1;
build(2*nod, pozx, mid);
build(2*nod + 1, mid + 1, pozy);
aint[nod].resize(aint[2*nod].size() + aint[2*nod + 1].size());
load(nod);
}
inline int cb(const int &nod) {
int j, pas = 1<<13, i;
for(i = 0; pas; pas>>=1)
if(i + pas < aint[nod].size() && aint[nod][i + pas] < val1)
i += pas;
if(aint[nod][i] >= val1)
--i;
pas = 1<<13;
for(j = 0; pas; pas>>=1)
if(j + pas < aint[nod].size() && aint[nod][j + pas] <= val2)
j += pas;
if(i>=j)
return 0;
return j - i;
}
void query(const int &nod, const int &pozx, const int &pozy) {
if(pozx>=x && pozy<=y) {
rez += cb(nod);
return;
}
int mid = (pozx + pozy)>>1;
if(mid >= x)
query(2*nod, pozx, mid);
if(mid < y)
query(2*nod + 1, mid + 1, pozy);
}
int main() {
int i, j, pas;
in >> n;
for(i = 1; i<=n; ++i)
in >> v[i].x >> v[i].y;
sort(v + 1, v + n + 1, cmp);
build(1, 1, n);
in >> m;
for(i = 1; i<=m; ++i) {
in >> x1 >> val1 >> x2 >> val2;
pas = 1<<13;
for(j = 0; pas; pas>>=1)
if(j + pas <= n && v[j + pas].x < x1)
j += pas;
x = j + 1;
pas = 1<<13;
for(j = 0; pas; pas>>=1)
if(j + pas <= n && v[j + pas].x <= x2)
j += pas;
y = j;
rez = 0;
query(1, 1, n);
out << rez << "\n";
}
return 0;
}