Cod sursa(job #79520)

Utilizator peanutzAndrei Homorodean peanutz Data 22 august 2007 22:47:48
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

#define NMAX 16100
#define pb push_back
#define sz size()

typedef struct punct
{
	int x, y;
};
punct p[NMAX];
int n, m;
int res, x1, y1, x2, y2;
int y[NMAX];

vector<int> a[NMAX*3];

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

bool comp(const punct &x, const punct &y)
{
     return (x.x < y.x);
}

#define mid(st, dr) (((st)+(dr))>>1)
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)+1)

void build(int n, int st, int dr)
{
    //a[n].clear();

	if(st == dr)
	{
        a[n].resize(1);
		a[n][0] = p[st].y;
		return ;
    }
	
	int m = mid(st, dr);
	build(left(n), st, m);
	build(right(n), m+1, dr);

	a[n].resize(dr-st+1);
	
	int i = 0, j = 0;
	
	while(i < m-st+1 || j < dr-m)
	{
		if(i == m-st+1)
		{
			a[n][i+j] = a[ right(n) ][j++];
			continue;
		}
		if(j == dr-m)
		{
			a[n][i+j] = a[ left(n) ][i++];
			continue;
		}

		if(a[ right(n) ][j] < a[ left(n) ][i])
			a[n][i+j] = a[ right(n) ][j++];
		else
			a[n][i+j] = a[ left(n) ][i++];
	}
    //printf("interval %d %d\n", st, dr);
    //for(i = 0; i < a[n].sz; ++i)
    //      printf("%d ", a[n][i]);
    //printf("\n");
}


int bs(int n)
{
	int st, dr, keep1 = -1, keep2 = -1, m;

	st = 0, dr = a[n].sz-1;

	while(st <= dr)
	{
		m = mid(st, dr);

		if(a[n][m] >= y1)
			keep1 = m, dr = m-1;
		else
			st = m+1;
		
		if(dr < 0)
			break;
	}
	
	if(keep1 == -1)
		return 0;

	
	st = 0, dr = a[n].sz-1;

	while(st <= dr)
	{
		m = mid(st, dr);

		if(a[n][m] <= y2)
			keep2 = m, st = m+1;
		else
			dr = m-1;
		
		if(dr < 0)
			break;
	}

	if(keep2 == -1)
		return 0;

	return keep2-keep1+1;
}

void query(int n, int st, int dr)
{
    //printf("%d %d\n", st, dr);
	if(p[st].x >= x1 && p[dr].x <= x2)
	{
        //printf("%d %d\n", st, dr);
		res += bs(n);
		return ;
	}	

	int m = mid(st, dr);

	if(p[m].x >= x1)
		query(left(n), st, m);

	if(p[m+1].x <= x2 && m+1 <= dr)
		query(right(n), m+1, dr);
}


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

    for(int i = 0; i < NMAX*3; ++i)
       a[i].clear();

	sort(p+1, p+n+1, comp);

	read();

	build(1, 1, n);
	
	//for(int i = 1; i <= n; ++i)
	//	printf("%d ", p[i].y);
	//printf("\n\n");

	scanf("%d", &m);
	for(int i = 1; i <= m; ++i)
	{
		scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
		res = 0;

		query(1, 1, n);
		
		printf("%d\n", res);
	}

	return 0;
}