Cod sursa(job #923948)

Utilizator razvan.popaPopa Razvan razvan.popa Data 23 martie 2013 23:24:54
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define pb push_back
#define point pair<int, int>
#define x first
#define y second
#define ls (node << 1)
#define rs ((node << 1) + 1)
#define FOR(i,a,b)\
   for(int i=a; i<=b; ++i)
#define infile "zoo.in"
#define outfile "zoo.out"
#define nMax 16005
using namespace std;

struct rectangle{
	int x1, y1, x2, y2;
} Rect;

point P[nMax];

vector < int > AI[nMax << 2];

int N, M;


void mergeLists(int node){
	unsigned int k = 0, l = 0, r = 0;

	AI[node].resize(AI[ls].size() + AI[rs].size());

	while(l < AI[ls].size() && r < AI[rs].size())
		if(AI[ls][l] < AI[rs][r])
			AI[node][k++] = AI[ls][l++];
		else
			AI[node][k++] = AI[rs][r++];

	while(l < AI[ls].size())
		AI[node][k++] = AI[ls][l++];

	while(r < AI[rs].size())
		AI[node][k++] = AI[rs][r++];
}

void buildTree(int node, int left, int right){
    if(left == right){
    	AI[node].pb(P[left].y);;
    	return;
    }

    int middle = (left + right) >> 1;

    buildTree(ls, left, middle);
    buildTree(rs, middle + 1, right);

    mergeLists(node);
}

int query(int node, int left, int right){
	if(Rect.x1 <= P[left].x && P[right].x <= Rect.x2)
		return lower_bound(AI[node].begin(), AI[node].end(), Rect.y2 + 1) - lower_bound(AI[node].begin(), AI[node].end(), Rect.y1);

	if(left == right)
		return 0;

	int res = 0, middle = (left + right) >> 1;

	if(Rect.x1 <= P[middle].x)
		res += query(ls, left, middle);
	if(Rect.x2 >= P[middle].x)
		res += query(rs, middle + 1, right);

	return res;
}

int main(){
    freopen(infile, "r", stdin);
    freopen(outfile, "w", stdout);

    scanf("%d", &N);

    FOR(i,1,N)
    	scanf("%d %d", &P[i].x, &P[i].y);

    sort(P + 1, P + N + 1);

    buildTree(1, 1, N);

    for(scanf("%d", &M); M; M--){
    	scanf("%d %d %d %d", &Rect.x1, &Rect.y1, &Rect.x2, &Rect.y2);

    	Rect.x1 = max(Rect.x1, P[1].x);
    	Rect.x2 = min(Rect.x2, P[N].x);

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

    fclose(stdin);
    fclose(stdout);

    return 0;
}