Pagini recente » Cod sursa (job #1503541) | Cod sursa (job #2245387) | Cod sursa (job #1860321) | Cod sursa (job #2639262) | Cod sursa (job #220434)
Cod sursa(job #220434)
#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, semn, x1, y1, x2, y2, p, q, sum, i1, i2;
int aib[MAX_L];
int intreb[MAX_L];
int ordon[MAX_L], v[MAX_L];
int qry[5][MAX_N];
char s[50];
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);
//citirea parsata
scanf("%d\n",&n);
for (i = 1; i <= n; v[i] = i, i++)
scanf("%d %d",&a[i].x, &a[i].y);
scanf("%d\n", &m);
for (i = 1; i <= m; i++) {
fgets(s,50,stdin);
j = 0;
semn = 1;x1 = 0;
if (s[j] == '-') {semn = -1; j++;}
for (j = j; s[j] != ' '; j++)
x1 = x1 * 10 + s[j] - '0';
x1 *= semn;
j++;
semn = 1; y1 = 0;
if (s[j] == '-') {semn = -1; j++;}
for (j = j; s[j] != ' '; j++)
y1 = y1 * 10 + s[j] - '0';
y1 *= semn;
j++;
semn = 1; x2 = 0;
if (s[j] == '-') {semn = -1; j++;}
for (j = j; s[j] != ' '; j++)
x2 = x2 * 10 + s[j] - '0';
x2 *= semn;
j++;
semn = 1; y2 = 0;
if (s[j] == '-') {semn = -1; j++;}
for (j = j; s[j] != '\n' && s[j] != '\0'; j++)
y2 = y2 * 10 + s[j] - '0';
y2 *= semn;
a[++n].x = x1 - 1; a[n].y = y1 - 1; intreb[n] = i;
a[++n].x = x1 - 1; a[n].y = y2; intreb[n] = i;
a[++n].x = x2; a[n].y = y1 - 1; intreb[n] = i;
a[++n].x = x2; a[n].y = y2; intreb[n] = i;
}
}
void inter2(int p, int q) {
int r = (p + q) / 2; k = 0, i1 = p, i2 = r + 1;
while (i1 <= r && i2 <= q) {
if (a[v[i1]].y < a[v[i2]].y) ordon[++k] = v[i1++];
else ordon[++k] = v[i2++];
}
while (i1 <= r) ordon[++k] = v[i1++];
while (i2 <= q) ordon[++k] = v[i2++];
k = 0;
for (i = p; i <= q; i++)
v[i] = ordon[++k];
}
void merge2(int p, int q) {
if (p >= q) return;
int r = (p + q) / 2;
merge2(p, r);
merge2(r + 1, q);
inter2(p, q);
}
void normalizare () {
p = 1; q = 1;
for (i = 1; i <= n; i++) {
b[i].x = p;
if (a[i].x > a[i - 1].x) b[i].x = ++p;
v[i] = i;
}
merge2(1, n);
for (i = 1; i <= n; i++) {
b[v[i]].y = q;
if (a[v[i]].y > a[v[i - 1]].y) b[v[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[i] == 0) update(b[i].y);
//query
if (intreb[i] != 0) {
p = intreb[i];
qry[++qry[0][p]][p] = query(b[i].y);
}
}
}
void inter(int p, int q) {
int r = (p + q) / 2; k = 0, i1 = p, i2 = r + 1;
while (i1 <= r && i2 <= q) {
if ((a[i1].x < a[i2].x) || (a[i1].x == a[i2].x && a[i1].y < a[i2].y)||
(a[i1].x == a[i2].x && a[i1].y == a[i2].y && intreb[i1] < intreb[i2])) {
b[++k].x = a[i1].x; b[k].y = a[i1].y; ordon[k] = intreb[i1]; i1++;
}
else { b[++k].x = a[i2].x; b[k].y = a[i2].y; ordon[k] = intreb[i2]; i2++;}
}
while (i1 <= r) {b[++k].x = a[i1].x; b[k].y = a[i1].y; ordon[k] = intreb[i1]; i1++;};
while (i2 <= q) {b[++k].x = a[i2].x; b[k].y = a[i2].y; ordon[k] = intreb[i2]; i2++;};
k = 0;
for (i = p; i <= q; i++) {
a[i].x = b[++k].x; a[i].y = b[k].y; intreb[i] = ordon[k];
}
}
void merge(int p, int q) {
if (p >= q) return;
int r = (p + q) / 2;
merge(p, r);
merge(r + 1, q);
inter(p, q);
}
void solve() {
//sortarea elementelor
merge(1, n);
//normalizarea elementelor
normalizare();
//parcurgerea elementelor si query - urile respective
parcurg();
}
void write() {
for (i = 1; i <= m; i++) {
sum = qry[4][i] - qry[2][i] - qry[3][i] + qry[1][i];
printf("%d\n",sum);
}
}
int main() {
cit();
solve();
write();
return 0;
}