Pagini recente » Cod sursa (job #2059962) | Cod sursa (job #3284956) | Cod sursa (job #1755307) | Cod sursa (job #66072) | Cod sursa (job #1517889)
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int NMAX = 16010;
const int MMAX = 100010;
const int NORMMAX = 220000;
struct query {int ind, x, y1, y2; bool isOne;} q[2 * MMAX]; //if !isOne, then it is four
struct point {int x, y;} v[NMAX];
int N, M;
int aib[NMAX];
vector<int> norm;
int ans[MMAX][4];
void updateAIB (int x, int val = 1) {
while (x <= NORMMAX) {
aib[x] += val;
x += (x & (-x));
}
}
int queryAIB (int pos) {
int ans = 0;
while (pos > 0) {
ans += aib[pos];
pos -= (pos & (-pos));
}
return ans;
}
bool critxq (query a, query b) {
return a.x < b.x;
}
bool critxv (point a, point b) {
return a.x < b.x;
}
int normval (int x) {
return (lower_bound (norm.begin (), norm.end (), x) - norm.begin ());
}
int main () {
freopen ("zoo.in", "r", stdin);
freopen ("zoo.out", "w", stdout);
scanf ("%d", &N);
for (int i = 1; i <= N; i++) {
scanf ("%d%d", &v[i].x, &v[i].y);
norm.push_back (v[i].y);
}
scanf ("%d", &M);
for (int i = 1, j = 1; i <= M; i++, j += 2) {
scanf ("%d%d%d%d", &q[j].x, &q[j].y1, &q[j + 1].x, &q[j + 1].y2);
q[j].x--;
q[j].y1--;
q[j].ind = q[j + 1].ind = i;
q[j].y2 = q[j + 1].y2;
q[j + 1].y1 = q[j].y1;
q[j].isOne = 1;
q[j + 1].isOne = 0;
norm.push_back (q[j].y1);
norm.push_back (q[j].y2);
}
sort (norm.begin (), norm.end ());
norm.erase (unique (norm.begin (), norm.end ()), norm.end ());
sort (q + 1, q + 2 * M + 1, critxq);
sort (v + 1, v + N + 1, critxv);
int crt = 1;
for (int i = 1; i <= 2 * M; i++) {
while (crt <= N && v[crt].x <= q[i].x) {
updateAIB (normval(v[crt].y) + 1);
crt++;
}
int ansp1 = queryAIB (normval(q[i].y1) + 1);
int ansp2 = queryAIB (normval(q[i].y2) + 1);
if (q[i].isOne) {
ans[q[i].ind][0] = ansp1;
ans[q[i].ind][1] = ansp2;
}
else {
ans[q[i].ind][2] = ansp1;
ans[q[i].ind][3] = ansp2;
}
}
for (int i = 1; i <= M; i++) {
int ANS;
ANS = ans[i][3] - ans[i][2] - ans[i][1] + ans[i][0];
printf ("%d\n", ANS);
}
return 0;
}