Pagini recente » Cod sursa (job #2380141) | Cod sursa (job #2481232) | Cod sursa (job #44137) | Cod sursa (job #716767) | Cod sursa (job #1233873)
#include <fstream>
#include <algorithm>
#include <vector>
#define pe pair<int, int>
#define mp make_pair
#define fi first
#define se second
using namespace std;
ifstream fin("zoo.in");
ofstream fout("zoo.out");
struct que {
int tip;
int x, y;
int poz;
que(int _tip = 0, int _x = 0, int _y = 0, int _poz = 0) {
tip = _tip;
x = _x;
y = _y;
poz = _poz;
}
inline bool operator < (const que &a) const {
if(x == a.x) {
if(y == a.y) {
return tip < a.tip;
}
return y < a.y;
}
return x < a.x;
}
};
const int MAX_N = 16100;
const int MAX_M = 100100;
const int INF = 2000000000;
vector<int> y;
vector<pe> A;
vector<pair<pe, pe> > Q;
vector<que> op;
int sol[MAX_M];
int aib[4 * MAX_M];
void update(int poz, int val) {
while(poz < 4 * MAX_M) {
aib[poz] += val;
poz += (poz & (-poz));
}
}
int query(int poz) {
int s = 0;
while(poz) {
s += aib[poz];
poz -= (poz & (-poz));
}
return s;
}
int main() {
int n, m;
fin >> n;
for(int i = 1; i <= n; i++) {
int a, b;
fin >> a >> b;
A.push_back(mp(a, b));
y.push_back(b);
}
fin >> m;
for(int i = 1; i <= m; i++) {
int x1, x2, y1, y2;
fin >> x1 >> y1 >> x2 >> y2;
y.push_back(y1);
y.push_back(y2);
Q.push_back(mp(mp(x1, y1), mp(x2, y2)));
}
y.push_back(-INF - 1);
sort(y.begin(), y.end());
y.erase(unique(y.begin(), y.end()), y.end());
for(auto it : A) {
int a = it.fi;
int b = lower_bound(y.begin(), y.end(), it.se) - y.begin();
op.push_back(que(0, a, b, 0));
}
for(auto i = 0; i < (int)Q.size(); i++) {
auto it = Q[i];
int x1 = it.fi.fi;
int y1 = lower_bound(y.begin(), y.end(), it.fi.se) - y.begin();
int x2 = it.se.fi;
int y2 = lower_bound(y.begin(), y.end(), it.se.se) - y.begin();
op.push_back(que(1, x1 - 1, y1 - 1, i + 1));
op.push_back(que(1, x2, y2, i + 1));
op.push_back(que(2, x1 - 1, y2, i + 1));
op.push_back(que(2, x2, y1 - 1, i + 1));
}
sort(op.begin(), op.end());
for(auto it : op) {
if(it.tip == 0) {
update(it.y, 1);
}
else if(it.tip == 1) {
sol[it.poz] += query(it.y);
}
else {
sol[it.poz] -= query(it.y);
}
}
for(int i = 1; i <= m; i++) {
fout << sol[i] << '\n';
}
return 0;
}