Pagini recente » Cod sursa (job #3192488) | Cod sursa (job #1522016) | Cod sursa (job #1512403) | Cod sursa (job #1481350) | Cod sursa (job #828893)
Cod sursa(job #828893)
#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 make_point(int x, int y, int type, int poz) {
point a;
a.x = x;
a.y = y;
a.type = type;
a.poz = poz;
return a;
}
int N, M, rez[MAXM], aib[DIMAIB];
vector<point> v;
vector<int> norm;
bool cmp (point a, point b) {
if (a.x == b.x)
if (a.type == 0)
return 1;
else 0;
return a.x < b.x;
}
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;
for (int i = 1; i <= N; ++i) {
int x, y;
fin >> x >> y;
v.push_back(make_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 (make_point(x1 - 1, y1 - 1, 1, i));
v.push_back (make_point(x1 - 1, y2, -1, i));
v.push_back (make_point(x2, y1 - 1, -1, i));
v.push_back (make_point(x2, y2, 1, i));
}
sort (v.begin(), v.end(), cmp);
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 = i;
//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;
}