Pagini recente » Cod sursa (job #2086140) | Cod sursa (job #984804) | Cod sursa (job #1070396) | Cod sursa (job #1373753) | Cod sursa (job #749953)
Cod sursa(job #749953)
#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;
}
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());
merge(aint[2*nod].begin(), aint[2*nod].end(), aint[2*nod + 1].begin(), aint[2*nod + 1].end(), aint[nod].begin());
}
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;
}