Cod sursa(job #219414)

Utilizator savimSerban Andrei Stan savim Data 6 noiembrie 2008 20:54:44
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <stdio.h>
#include <algorithm>

using namespace std;

#define MAX_N 100000
#define MAX_L 517000
#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;
	}
}

int lsb(int x) {
	return x ^ (x & (x - 1));
}

void update(int k) {
	while (k <= q) {
	    aib[k]++;
		k += lsb(k);
	}
}

int query(int k) {
	sum = 0;
	while (k) {
		sum += aib[k];
		k -= lsb(k);
	}
	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) {
		if (a[p].x < a[q].x) return true;
		else return false;
	}
	else {
		if (a[p].y < a[q].y) return true;
		else if (a[p].y > a[q].y) return false;
			 else 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;
}