Cod sursa(job #220520)

Utilizator savimSerban Andrei Stan savim Data 11 noiembrie 2008 11:54:48
Problema Zoo Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.35 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 200000
#define MAX_L 417000
#define inf 2147000000

int n, m, i, j, k, x1, y1, x2, y2, p, q, sum, cop;
int aib[MAX_L];
int intreb[MAX_L];
int ordon[MAX_N], vord[MAX_N];
int qry[5][MAX_N];
int init[MAX_N], norm[MAX_N];

struct punct {
	int x;
	int y;
};

punct a[MAX_L], b[MAX_L], v[MAX_N];

void cit() {
	freopen("zoo.in", "r", stdin);
	freopen("zoo.out", "w", stdout);
	
	scanf("%d", &n); cop = n;
	for (i = 1; i <= n; i++)
		scanf("%d %d", &a[i].x, &a[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)) {
              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);
}

inline int cmp(int a, int b) {
	return ordon[a] < ordon[b];
}

void normalizare () {
	p = 1; q = 1;
	for (i = 1; i <= n; i++) {
		v[i].x = a[i].x;
		
		ordon[i]  = a[i].y;
		vord[i] = i;
	}

	sort(vord + 1, vord + n + 1, cmp);

	ordon[0] = inf;
	for (i = 1; i <= n; i++) {
		init[i] = a[vord[i]].y;

		v[vord[i]].y = q;
		if (ordon[vord[i]] > ordon[vord[i - 1]]) v[vord[i]].y = ++q;
		
		norm[i] = 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;
}

int caut_binar(int k) {
	int p = 0, q = n + 1, r, sol = 0;
	
	while (p + 1 < q) {
		r = (p + q) / 2;
		if (init[r] >= k) {
			sol = q = r;
			if (init[r] != k) sol = r - 1;
		}
		else p = r;
	}
	
	if (init[n] < k) sol = n;
	if (k < init[1]) sol = 0;
	
	return norm[sol];
}

void parcurg() {
	j = 1; n = cop;
	
	for (i = 1; i <= n; i++) {
		//query
		while (a[j].x < v[i].x) {
      	    p = intreb[j];
			qry[++qry[0][p]][p] = query(caut_binar(a[j].y));
			j++;
		} 
		
		//update
		update(v[i].y);
	}
	
	for (i = j; i <= 4 * m; i++) {
		p = intreb[i];
		qry[++qry[0][p]][p] = query(caut_binar(a[i].y));
	}
}

void solve() {
	//sortarea elementelor
	merge(1, n);

	//normalizarea elementelor
	normalizare();
	
	scanf("%d", &m); n = 0;
	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; 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;
	}	

	merge(1, n);

	//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;
}