Pagini recente » Cod sursa (job #1143002) | Cod sursa (job #2670114) | Cod sursa (job #852060) | Cod sursa (job #699232) | Cod sursa (job #749958)
Cod sursa(job #749958)
#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 = 16110;
int n, m, x1, val1, x2, val2, x, y, rez;
pct v[N];
vector<int> aint[4*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());
}
void query(const int &nod, const int &pozx, const int &pozy) {
if(pozx>=x && pozy<=y) {
rez += lower_bound(aint[nod].begin(), aint[nod].end(), val2 + 1) - lower_bound(aint[nod].begin(), aint[nod].end(), val1);
return;
}
int mid = (pozx + pozy)>>1;
if(mid >= x)
query(2*nod, pozx, mid);
if(mid < y)
query(2*nod + 1, mid + 1, pozy);
}
char buff[101];
int p;
inline int ter() {
int t = 0, ver = 0;
if(buff[p] == '-') {
ver = 1;
++p;
}
while(buff[p] >= '0' && buff[p] <= '9')
t = t * 10 + buff[p++] - '0';
++p;
return ver ? -t : t;
}
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;
in.get();
for(i = 1; i<=m; ++i) {
in.getline(buff, 100); p =0;
x1 = ter();
val1 = ter();
x2 = ter();
val2 = ter();
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;
}