Cod sursa(job #503906)

Utilizator katakunaCazacu Alexandru katakuna Data 25 noiembrie 2010 17:10:30
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define Nmax 16010

struct punct {
	int x, y;
} P[Nmax];

int j, n, m, x1, y1, x2, y2, sol;
vector <int> A[4 * Nmax];

int cmp (const punct &a,const punct &b) {
	return a.x < b.x;	
}

void citire () {

	scanf ("%d", &n);
	for (int i = 1; i <= n; i++) 
		scanf ("%d %d", &P[i].x, &P[i].y);
	scanf ("%d", &m);                      

	sort (P + 1, P + n + 1, cmp);
}

void make_arb (int nod, int st, int dr) {

	if (st == dr) {
		A[nod].push_back (st);
		return ;
	}

	int MIJ = (st + dr) >> 1, N1 = nod << 1, N2 = (nod << 1) + 1;

	make_arb (N1, st, MIJ);
	make_arb (N2, MIJ + 1, dr);  	

    vector <int>::iterator i, j;
	for (i = A[N1].begin (), j = A[N2].begin (); i != A[N1].end () || j != A[N2].end ();) 
		if (j == A[N2].end () || (i != A[N1].end () && P[*i].y < P[*j].y))
			A[nod].push_back (*i), i++;
		else
			A[nod].push_back (*j), j++;
}

int binar (int nod) {

	int p = 0, u = A[nod].size () - 1, mij, a;
	while (p <= u) {
		mij = (p + u) >> 1;
		if (P[A[nod][mij]].y >= y1) 
			u = mij - 1;
		else
			p = mij + 1;
	}

	a = p;

	p = 0; u = A[nod].size () - 1; 
	while (p <= u) {
		mij = (p + u) >> 1;
		if (P[A[nod][mij]].y <= y2)
			p = mij + 1;
		else
			u = mij - 1;
	}

	
   return u - a + 1; 
}

void query (int nod, int st, int dr) {
	
	if (x1 <= P[st].x && P[dr].x <= x2) {
		sol+= binar (nod);	
		return ;
	}

	if (st == dr) return ;

	int MIJ = (st + dr) >> 1, N1 = nod << 1, N2 = (nod << 1) + 1;

	if (x1 <= P[MIJ].x) query (N1, st, MIJ);
	if (P[MIJ+1].x <= x2) query (N2, MIJ + 1, dr);
}

void rezolva () {
	
	make_arb (1, 1, n);

	for (int i = 1; i <= m; i++) {
		scanf ("%d %d %d %d", &x1, &y1, &x2, &y2);
        sol = 0; query (1, 1, n);
		printf ("%d\n", sol);                                                                         
	}
	
}

int main () {

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

	citire ();
	rezolva ();
	
	return 0;
}