Cod sursa(job #495424)

Utilizator toni2007Pripoae Teodor Anton toni2007 Data 25 octombrie 2010 10:56:46
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define maxN 	100100
#define x 		first
#define y 		second

int X1[maxN], X2[maxN], Y1[maxN], Y2[maxN], N, M, aib[3 * maxN], in[maxN], out[maxN];
pair <int, int> P[maxN];
struct ev {
	int x, type, ind;
};
vector <ev> _ev;
vector <int> aux1, aux2;

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

inline bool cmp (ev a, ev b) {
	if (a.x != b.x)
		return a.x < b.x;
	return a.type < b.type;
}

int query (int poz) {
	int sum = 0;
	for (; poz; poz -= lsb(poz))
		sum += aib[poz];
	return sum;
}

void update (int poz) {
//	fprintf(stderr, "%d\n", poz);
	for (; poz <= N + 2 * M; poz += lsb(poz))
		aib[poz] ++;
}

int main () {
	int i;

	freopen("zoo.in", "r", stdin);
	freopen("zoo.out", "w", stdout);

	scanf("%d", &N);

	for (i = 1; i <= N; ++ i)
		scanf("%d%d", &P[i].x, &P[i].y),
		aux1.push_back(P[i].x),
		aux2.push_back(P[i].y);

	scanf("%d", &M);

	for (i = 1; i <= M; ++ i) {
		scanf("%d%d%d%d", &X1[i], &Y1[i], &X2[i], &Y2[i]);
		aux1.push_back(X1[i]);
		aux1.push_back(X2[i]);
		aux2.push_back(Y1[i]);
		aux2.push_back(Y2[i]);
	}

	sort(aux1.begin(), aux1.end());
	sort(aux2.begin(), aux2.end());
	aux1.resize(unique(aux1.begin(), aux1.end()) - aux1.begin());
	aux2.resize(unique(aux2.begin(), aux2.end()) - aux2.begin());

	for (i = 1; i <= N; ++ i) {
		P[i].x = lower_bound(aux1.begin(), aux1.end(), P[i].x) - aux1.begin() + 1;
		P[i].y = lower_bound(aux2.begin(), aux2.end(), P[i].y) - aux2.begin() + 1;
	//	fprintf(stderr, "%d %d\n", P[i].x, P[i].y);
	}

	for (i = 1; i <= M; ++ i) {
		X1[i] = lower_bound(aux1.begin(), aux1.end(), X1[i]) - aux1.begin() + 1;
		X2[i] = lower_bound(aux1.begin(), aux1.end(), X2[i]) - aux1.begin() + 1;
		Y1[i] = lower_bound(aux2.begin(), aux2.end(), Y1[i]) - aux2.begin() + 1;
		Y2[i] = lower_bound(aux2.begin(), aux2.end(), Y2[i]) - aux2.begin() + 1;
	}

	for (i = 1; i <= N; ++ i)
		_ev.push_back((ev) {P[i].x, 2, i});
	for (i = 1; i <= M; ++ i) {
		_ev.push_back((ev) {X1[i], 1, i});
		_ev.push_back((ev) {X2[i], 3, i});
	}

	sort(_ev.begin(), _ev.end(), cmp);

	for (i = 0; i < (int) _ev.size(); ++ i) {
		if (_ev[i].type == 1) {
			in[_ev[i].ind] = query(Y2[_ev[i].ind]) - query(Y1[_ev[i].ind] - 1);
//			printf("x %d %d\n", query(Y2[_ev[i].ind]), query(Y1[_ev[i].ind] - 1));
		}
		else if (_ev[i].type == 3) {
			out[_ev[i].ind] = query(Y2[_ev[i].ind]) - query(Y1[_ev[i].ind] - 1);
//			printf("xy %d %d\n", query(Y2[_ev[i].ind]), query(Y1[_ev[i].ind] - 1));
		}
		else
			update(P[_ev[i].ind].y);
	}

//	printf("y %d %d\n", query(5), query(3));
	for (i = 1; i <= M; ++ i)
		printf("%d\n", out[i] - in[i]);
}