Pagini recente » Cod sursa (job #1119772) | Cod sursa (job #2318842) | Cod sursa (job #1311968) | Cod sursa (job #140242) | Cod sursa (job #219418)
Cod sursa(job #219418)
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAX_N 100000
#define MAX_L 417000
#define inf 2147000000
int n, m, i, j, k, x1, y1, x2, y2, p, q, sum;
int aib[MAX_L];
int intreb[MAX_L][2], v[MAX_L];
int ordon[MAX_L], vord[MAX_L];
int qry[MAX_N][5];
struct punct {
int x;
int y;
};
punct a[MAX_L], b[MAX_L];
void cit() {
freopen("zoo.in", "r", stdin);
freopen("zoo.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= n; v[i] = i, i++)
scanf("%d %d", &a[i].x, &a[i].y);
scanf("%d", &m);
for (i = 1; i <= m; i++) {
scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
a[++n].x = x1 - 1; a[n].y = y1 - 1; v[n] = n; intreb[n][0] = i;
a[++n].x = x1 - 1; a[n].y = y2; v[n] = n; intreb[n][0] = i;
a[++n].x = x2; a[n].y = y1 - 1; v[n] = n; intreb[n][0] = i;
a[++n].x = x2; a[n].y = y2; v[n] = n; intreb[n][0] = i;
}
}
inline int cmp2(int a, int b) {
return ordon[a] < ordon[b];
}
void normalizare () {
p = 1; q = 1;
for (i = 1; i <= n; i++) {
b[i].x = p;
if (a[v[i]].x > a[v[i - 1]].x) b[i].x = ++p;
ordon[i] = a[v[i]].y;
vord[i] = i;
}
sort(vord + 1, vord + n + 1, cmp2);
for (i = 1; i <= n; i++) {
b[vord[i]].y = q;
if (ordon[vord[i]] > ordon[vord[i - 1]]) b[vord[i]].y = ++q;
}
}
void update(int k) {
while (k <= q) {
aib[k]++;
k += k ^ (k & (k - 1));
}
}
int query(int k) {
sum = 0;
while (k) {
sum += aib[k];
k -= k ^ (k & (k - 1));
}
return sum;
}
void parcurg() {
for (i = 1; i <= n; i++) {
//update
if (intreb[v[i]][0] == 0) update(b[i].y);
//query
if (intreb[v[i]][0] != 0) intreb[v[i]][1] = query(b[i].y);
}
}
inline int cmp(int p, int q) {
if (a[p].x != a[q].x) return a[p].x < a[q].x;
else {
if (a[p].y != a[q].y) return a[p].y < a[q].y;
if (intreb[p][0] != 0 && intreb[q][0] == 0) return false;
else return true;
}
}
void solve() {
//sortarea elementelor
sort(v + 1, v + n + 1, cmp);
//normalizarea elementelor
normalizare();
//parcurgerea elementelor si query - urile respective
parcurg();
//updatez valorile intrebarilor
for (i = 1; i <= n; i++)
if (intreb[v[i]][0] != 0) {
p = intreb[v[i]][0];
qry[p][++qry[p][0]] = intreb[v[i]][1];
}
}
void write() {
for (i = 1; i <= m; i++) {
sum = qry[i][4] - qry[i][2] - qry[i][3] + qry[i][1];
printf("%d\n",sum);
}
}
int main() {
cit();
solve();
write();
return 0;
}