Cod sursa(job #742500)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 30 aprilie 2012 15:19:59
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.68 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
struct punct {
	int x,y;
};
vector <int> a[400001];
punct v[16001],p[100001],q[100001];
int x[500001],y[500001],n,nr,sf1,sf2,aa,bb,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;
}
int cautarebinara(int y[], int p, int q, int val, int o)
{
	int mij,poz;
	poz=-1;
	while(p<=q) {
		mij=(p+q)/2;
		if(val<y[mij])
			q=mij-1;
		else if(val>y[mij])
			p=mij+1;
		else {
			poz=mij;
			break;
		}
	}
	if(poz>0) {
		if(o==1)
			while((poz>1)&&(y[poz]==y[poz-1]))
				poz--;
		else 
			while(y[poz]==y[poz+1])
				poz++;
	}
	return poz;
}
int cautarebinara1(vector <int> y ,int p, int q, int val)
{
	int mij,poz;
	if(y[0]>=val)
		return 0;
	poz=-1;
	while(p<=q) {
		mij=(p+q)/2;
		if(val<y[mij])
			q=mij-1;
		else if(val>y[mij]) {
			poz=mij;
			p=mij+1;
		}
		else {
			poz=mij;
			break;
		}
	}
	if(poz<=0)
		return poz;
	while(y[poz]==y[poz+1])
		poz++;
	return poz;
}
int cautarebinara2(vector <int> y ,int p, int q, int val)
{
	int mij,poz;
	if(y[q]<=val)
		return q;
	poz=-1;
	while(p<=q) {
		mij=(p+q)/2;
		if(val<y[mij]) {
			poz=mij;
			q=mij-1;
		}
		else if(val>y[mij]) 
			p=mij+1;
		else {
			poz=mij;
			break;
		}
	}
	if(poz<=0)
		return poz;
	while(y[poz]==y[poz-1])
		poz--;
	return poz;
}
void construieste(int nod, int st, int dr)
{
	int mij,i,j,nn,m,p,q;
	if(st==dr) {
		p=cautarebinara(y,1,nr,st,1);
		q=cautarebinara(y,1,nr,st,2);
		if((p<1)||(q<1))
			return;
		for(i=p;i<=q;i++)
			a[nod].push_back(v[i].y);
		return ;
	}
	mij=(st+dr)/2;
	construieste(nod*2,st,mij);
	construieste(nod*2+1,mij+1,dr);
	nn=a[nod*2].size()-1;
	m=a[nod*2+1].size()-1;
	i=0;
	j=0;
	while((i<=nn)&&(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<=nn;i++)
		a[nod].push_back(a[nod*2][i]);
	for( ;j<=m;j++)
		a[nod].push_back(a[nod*2+1][j]);
}
void normalizare(int n, int m)
{
	int i,l,k;
	l=0;
	for(i=1;i<=n;i++) {
		l++;
		x[l]=v[i].x;
		l++;
		x[l]=v[i].y;
	}
	for(i=1;i<=m;i++) {
		l++;
		x[l]=p[i].x;
		l++;
		x[l]=p[i].y;
		l++;
		x[l]=q[i].x;
		l++;
		x[l]=q[i].y;
	}
	sort(x+1,x+l+1);
	k=0;
	for(i=1;i<=l;i++) {
		while((x[i]==x[i+1])&&(i<=l))
			i++;
		k++;
		y[k]=x[i];
	}
	l=k;
	for(i=1;i<=n;i++){
		v[i].x=cautarebinara(y,1,l,v[i].x,1);
		v[i].y=cautarebinara(y,1,l,v[i].y,1);
	}
	for(i=1;i<=m;i++) {
		p[i].x=cautarebinara(y,1,l,p[i].x,1);
		p[i].y=cautarebinara(y,1,l,p[i].y,1);
		q[i].x=cautarebinara(y,1,l,q[i].x,1);
		q[i].y=cautarebinara(y,1,l,q[i].y,1);
	}
}
void query(int nod, int st, int dr)
{
	int mij;
	if((aa<=st)&&(dr<=bb)) {
		int x,y;
		x=cautarebinara1(a[nod],0,a[nod].size()-1,sf1);
		if(x<0)
			return;
		y=cautarebinara2(a[nod],0,a[nod].size()-1,sf2);
		if(y<0)
			return;
		val=val+y-x+1;
		return;
	}
	mij=(st+dr)/2;
	if(aa<=mij)
		query(nod*2,st,mij);
	if(mij<bb)
		query(nod*2+1,mij+1,dr);
}
int main ()
{
	int i,m,j,max,mm;
	ifstream f("zoo.in");
	ofstream g("zoo.out");
	f>>n;
	for(i=1;i<=n;i++) 
		f>>v[i].x>>v[i].y;
	f>>m;
	for(i=1;i<=m;i++)
		f>>p[i].x>>p[i].y>>q[i].x>>q[i].y;
	normalizare(n,m);
	sort(v+1,v+n+1,cmp);
	max=0;
	for(i=1;i<=n;i++) {
		if(v[i].x>max)
			max=v[i].x;
		if(v[i].y>max)
			max=v[i].y;
		y[i]=v[i].x;
	}
	nr=n;
	n=max;
	construieste(1,1,n);
	f.close();
	for(i=1;i<=m;i++) {
		aa=p[i].x;
		bb=q[i].x;
		sf1=p[i].y;
		sf2=q[i].y;
		val=0;
		query(1,1,n);
		g<<val<<'\n';
	}
	g.close();
	return 0;
}