Cod sursa(job #923834)

Utilizator razvan.popaPopa Razvan razvan.popa Data 23 martie 2013 21:36:48
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.13 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define pb push_back
#define mkp make_pair
#define INF (1 << 30)
#define point pair<int, int>
#define x first
#define y second
#define ls (unsigned int)(node << 1)
#define rs (unsigned int)((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 <= left && right <= Rect.x2)
		return lower_bound(AI[node].begin(), AI[node].end(), Rect.y2 + 1) - lower_bound(AI[node].begin(), AI[node].end(), Rect.y1);

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

	if(Rect.x1 <= middle)
		res += query(ls, left, middle);
	if(Rect.x2 > middle)
		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 = lower_bound(P + 1, P + N + 1, mkp(Rect.x1, -INF)) - P;
    	Rect.x2 = lower_bound(P + 1, P + N + 1, mkp(Rect.x2, -INF)) - P;

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

    fclose(stdin);
    fclose(stdout);

    return 0;
}