Cod sursa(job #923873)

Utilizator razvan.popaPopa Razvan razvan.popa Data 23 martie 2013 22:11:10
Problema Zoo Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 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], X, SweepLine[nMax];

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] = SweepLine[left];
    	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 upper_bound(AI[node].begin(), AI[node].end(), Rect.y2) - 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;
}

void process(){
	sort(X.begin(), X.end());

	X.resize(distance(X.begin(), unique(X.begin(), X.end())));

	FOR(i,1,N){
		int pos = lower_bound(X.begin(), X.end(), P[i].x) - X.begin() + 1;
		SweepLine[pos].pb(P[i].y);
	}

	N = X.size();

	buildTree(1, 1, N);
}

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);
    	X.pb(P[i].x);
    }

    process();

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

    	Rect.x1 = lower_bound(X.begin(), X.end(), Rect.x1) - X.begin() + 1;
    	Rect.x2 = lower_bound(X.begin(), X.end(), Rect.x2) - X.begin() + 1;

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

    fclose(stdin);
    fclose(stdout);

    return 0;
}