Cod sursa(job #742700)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 1 mai 2012 08:28:31
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
struct punct {
	int x,y;
};
vector <int> a[4000001];
punct v[100001];
int 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) {
		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 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;
	sort(v+1,v+n+1,cmp);
	construieste(1,1,n);
	f>>m;
	for(i=1;i<=m;i++);
	f.close();
	g.close();
	return 0;
}