Cod sursa(job #391175)

Utilizator mihai_floreaFlorea Mihai Alexandru mihai_florea Data 5 februarie 2010 10:48:26
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.36 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef pair<int,int> punct;
const int NMAX=16001;
int N,M;
vector<punct> V;
vector<int> A[4*NMAX+1];
void build(int n,int l,int r)
{
	if (l==r)
	{
		A[n].resize(1,V[l].y);
		return;
	}
	int m=(l+r)/2;
	build(2*n  ,l  ,m);
	build(2*n+1,m+1,r);
	A[n].resize(A[2*n].size() + A[2*n+1].size());
	merge(A[2*n].begin(),A[2*n].end(),A[2*n+1].begin(),A[2*n+1].end(),A[n].begin());
}
int query(int n,int l,int r,int st,int dr,int jos,int sus)
{
	if (st<=V[l].x && V[r].x<=dr)
		return lower_bound(A[n].begin(),A[n].end(),sus+1)-lower_bound(A[n].begin(),A[n].end(),jos);
	if (l==r) return 0;
	int m=(l+r)/2;
	if (V[m+1].x>dr) return query(2*n,l,m,st,dr,jos,sus);
	else 
	if (V[m].x<st) return query(2*n+1,m+1,r,st,dr,jos,sus);
	else
	return query(2*n,l,m,st,V[m].x,jos,sus)+query(2*n+1,m+1,r,V[m+1].x,dr,jos,sus);
}
int main()
{
	int i,x,y,x_st,x_dr,y_jos,y_sus;
	ifstream fin("zoo.in");
	ofstream fout("zoo.out");
	fin>>N;
	V.reserve(N);
	for(i=0;i<N;++i)
	{
		fin>>x>>y;
		V.push_back(punct(x,y));
	}
	sort(V.begin(),V.end());
	build(1,0,N-1);
	fin>>M;
	while (M--)
	{
		fin>>x_st>>y_jos>>x_dr>>y_sus;
		x_st=max(x_st,V[0].x);
		x_dr=min(x_dr,V.back().x);
		fout<<query(1,0,N-1,x_st,x_dr,y_jos,y_sus)<<'\n';
	}
	return 0;
}