Pagini recente » Cod sursa (job #1387965) | Cod sursa (job #514086) | Cod sursa (job #321570) | Cod sursa (job #1139431) | Cod sursa (job #828896)
Cod sursa(job #828896)
#include <fstream>
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
#define MAXM 110000
#define DIMAIB 510000
ifstream fin ("zoo.in");
ofstream fout("zoo.out");
struct point {
int x, y, type, poz;
point(int xx, int yy, int t, int p) {
x = xx;
y = yy;
type = t;
poz = p;
}
bool operator < (const point &other) const {
if (x == other.x) {
if (type == 0) {
return true;
} else {
return false;
}
}
return x < other.x;
}
};
int N, M, rez[MAXM], aib[DIMAIB];
vector<point> v;
vector<int> norm;
inline void insert_aib(int poz, int elem) {
while (poz <= DIMAIB) {
aib[poz] += elem;
poz += poz & (-poz);
}
}
inline int query(int poz) {
int sum = 0;
while (poz > 0) {
sum += aib[poz];
poz -= poz & (-poz);
}
return sum;
}
int main() {
fin >> N;
v.reserve(DIMAIB);
norm.reserve(DIMAIB);
for (int i = 1; i <= N; ++i) {
int x, y;
fin >> x >> y;
v.push_back(point(x, y, 0, 0));
}
fin >> M;
for (int i = 1; i <= M; ++i) {
int x1, y1, x2, y2;
fin >> x1 >> y1 >> x2 >> y2;
norm.push_back(y1);
norm.push_back(y2);
norm.push_back(y1 - 1);
norm.push_back(y2 - 1);
v.push_back (point(x1 - 1, y1 - 1, 1, i));
v.push_back (point(x1 - 1, y2, -1, i));
v.push_back (point(x2, y1 - 1, -1, i));
v.push_back (point(x2, y2, 1, i));
}
sort (v.begin(), v.end());
sort (norm.begin(), norm.end());
norm.resize(unique(norm.begin(), norm.end()) - norm.begin());
for (int i = 0; i < v.size(); ++i)
v[i].y = lower_bound(norm.begin(), norm.end(), v[i].y) - norm.begin() + 1;
for (int i = 0; i < v.size(); ++i) {
//cerr << "query " << v[i].x << " " << v[i].y << " " << v[i].type << " " << v[i].poz << "\n";
switch(v[i].type) {
case 0: {
insert_aib(v[i].y, 1);
break;
}
case -1: {
rez[v[i].poz] -= query (v[i].y);
break;
}
case 1: {
rez[v[i].poz] += query (v[i].y);
break;
}
}
}
for (int i = 1; i <= M; ++i)
fout << rez[i] << "\n";
return 0;
}