Cod sursa(job #742703)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 1 mai 2012 08:50:46
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
struct punct {
	int x,y;
};
vector <int> a[4000001];
punct v[16001];
vector <int> vx;
int n,y1,y2,x1,x2,val;
inline bool cmp(const punct &a, const punct &b)
{
	if(a.y==b.y)
		return a.y<b.y;
	return a.x<b.x;
}
void construieste(int nod, int st, int dr)
{
	int mij,i,j,n,m;
	if(st==dr) {
		a[nod].push_back(v[st].y);
		return ;
	}
	mij=(st+dr)/2;
	construieste(nod*2,st,mij);
	construieste(nod*2+1,mij+1,dr);
	n=a[nod*2].size()-1;
	m=a[nod*2+1].size()-1;
	i=0;
	j=0;
	while((i<=n)&&(j<=m)) {
		if(a[nod*2][i]<a[nod*2+1][j]) {
			a[nod].push_back(a[nod*2][i]);
			i++;
		}
		else if(a[nod*2][i]>=a[nod*2+1][j]) {
			a[nod].push_back(a[nod*2+1][j]);
			j++;
		}
	}
	for( ;i<=n;i++)
		a[nod].push_back(a[nod*2][i]);
	for( ;j<=m;j++)
		a[nod].push_back(a[nod*2+1][j]);
}
void query(int nod, int st, int dr)
{
	int mij;
	if((x1<=st)&&(dr<=x2)) {
		int x,y;
		x=lower_bound(a[nod].begin(),a[nod].end(),y1)-a[nod].begin()+1;
		y=upper_bound(a[nod].begin(),a[nod].end(),y2)-a[nod].begin();
		val=val+y-x+1;
		return;
	}
	mij=(st+dr)/2;
	if(x1<=mij)
		query(nod*2,st,mij);
	if(mij<x2)
		query(nod*2+1,mij+1,dr);
}
int main ()
{
	int i,m,aa,bb;
	ifstream f("zoo.in");
	ofstream g("zoo.out");
	f>>n;
	for(i=1;i<=n;i++) 
		f>>v[i].x>>v[i].y;
	sort(v+1,v+n+1,cmp);
	construieste(1,1,n);
	for(i=1;i<=n;i++)
		vx.push_back(v[i].x);
	f>>m;
	for(i=1;i<=m;i++) {
		f>>aa>>y1>>bb>>y2;
		x1=lower_bound(vx.begin(),vx.end(),aa)-vx.begin()+1;
		x2=upper_bound(vx.begin(),vx.end(),bb)-vx.begin();
		if(x2>n)
			x2=n;
		val=0;
		query(1,1,n);
		g<<val<<'\n';
	}
	f.close();
	g.close();
	return 0;
}