Cod sursa(job #530437)

Utilizator ilincaSorescu Ilinca ilinca Data 7 februarie 2011 19:41:46
Problema Zoo Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <stdio.h>
#include <vector>
#include <algorithm>

#define nmax 16005
#define pmax 17*nmax
#define x first
#define y second

using namespace std;

typedef pair <int, int> ii;

int a, b, n, q, num, v [pmax];
ii c1, c2;
ii p [nmax];
ii arb [pmax];

void scan ()
{
	int i;
	scanf ("%d", &n);
	for (i=1; i <= n; ++i)
		scanf ("%d%d", &p [i].x, &p [i].y);
	sort (p+1, p+1+n);
}

ii interclasare (ii s1, ii s2)
{
	ii poz;
	++s1.y;
	++s2.y;
	poz.x=num+1;
	while (! (s1.x == s1.y || s2.x == s2.y))
	{
		if (v [s1.x] < v [s2.x])
			v [++num]=v [s1.x++];
		else
			v [++num]=v [s2.x++];

	}
	if (s1.x == s1.y)
		s1=s2;
	while (s1.x != s1.y)
	{
		v [++num]=v [s1.x++];
	}
	poz.y=num;
	return poz;
}

void cnstr (int st, int dr, int nod)
{
	if (st == dr)
	{
		v [++num]=p [st].y;
		arb [nod].x=arb [nod].y=num;
		return;
	}
	int m=(st+dr)>>1;
	cnstr (st, m, nod<<1);
	cnstr (m+1, dr, (nod<<1)+1);
	arb [nod]=interclasare (arb [nod<<1], arb [(nod<<1)+1]); //returneaza colturile stanga si dreapta ale ultimei secvente
//	fprintf (stderr, "\n\n\n%d\n", nod);
//	for (int i=arb [nod].x; i <= arb [nod].y; ++i)
//		fprintf (stderr, "%d ", v [i]);
}

int query (int st, int dr, int nod)
{
	if (a <= st && b >= dr)
		return (upper_bound (v+arb [nod].x, v+arb [nod].y+1, c2.y) - lower_bound (v+arb [nod].x, v+arb [nod].y+1, c1.y));
	int m=(st+dr)>>1, q=0;
	if (a <= m)
		q += query (st, m, nod<<1);
	if (m < b)
		q += query (m+1, dr, (nod<<1)+1);
	return q;
}

int main ()
{
	freopen ("zoo.in", "r", stdin);
	freopen ("zoo.out", "w", stdout);
	int i, q;
	scan ();
	cnstr (1, n, 1);
	scanf ("%d", &q);
	for (i=1; i <= q; ++i)
	{
		scanf ("%d %d %d %d", &c1.x, &c1.y, &c2.x, &c2.y);
		a=lower_bound (p+1, p+1+n, c1)-p;
		b=upper_bound (p+1, p+1+n, c2)-p-1;
//		fprintf (stderr, "query: a: %d   b: %d\n", a, b);
		printf ("%d\n", query (1, n, 1));
	}	
	return 0;
}