Cod sursa(job #523607)

Utilizator Andreid91Ciocan Andrei Andreid91 Data 18 ianuarie 2011 17:25:37
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include<fstream.h>
#include<algorithm>
#include<vector>


using namespace std;

ifstream f("zoo.in");
ofstream g("zoo.out");

int l,n,log,ai[20][20000],y1,y2,sol,x[20000],y[20000];

vector < pair<int, int>  > v;

inline int cmp (pair <int , int > a, pair <int, int> b)  { return a.first<=b.first;}

void querry( int niv, int st, int dr , int a, int b)
{
	if (a<=st && b>=dr)
	{
		int s=0,s2=0,p;
		for (p=log;p;p>>=1)
			if (p+s<=dr && p+s>=st && y1>ai[niv][p+s])
				s+=p;
			else if (p+s<st)
				s+=p;
		s++;
		for (p=log;p;p>>=1)
			if (p+s2<=dr && p+s2>=st && y2>=ai[niv][p+s2])
				s2+=p;
			else if (p+s2<st)
				s2+=p;
		if (s2-s>=0)
			sol+=s2-s+1;
		return ;
	}
	
	int mij=(st+dr)/2;
	if (mij>=a)
		querry(niv+1,st, mij,a,b);
	if (mij<b)
		querry (niv+1,mij+1, dr,a,b);
}
				

void solve()
{
	int x1,x2,p,s1,s2,m;
	f>>m;
	for (;m;--m)
	{
		f>>x1>>y1>>x2>>y2;
		if (x2<v[1].first || x1>v[n].first)
			g<<0<<'\n';
		else
		{
			
		for (s1=0,p=log;p;p>>=1)
			if (s1+p<n && x1>v[s1+p].first)
				s1+=p;
		s1++;
		for (s2=0,p=log;p;p>>=1)
			if (s2+p<=n && v[s2+p].first<=x2)
				s2+=p;
		sol=0;
		querry(1,1,n,s1,s2);
		g<<sol<<'\n';
		}
	}
	g.close();
	f.close();
}

void build (int niv,int st, int dr)
{
	if (st==dr)
	{
		ai[niv][st]=v[st].second;
		return;
	}
	int mij=( st+dr)/2,i,j;
	build (niv+1,st, mij);
	build (niv+1,mij+1,dr);
	
	int k=st-1;
	for (i=st,j=mij+1;i<=mij && j<=dr;)
		if (ai[niv+1][i]<ai[niv+1][j])
			ai[niv][++k]=ai[niv+1][i],++i;
		else
			ai[niv][++k]=ai[niv+1][j],++j;
	for (;i<=mij;++i)
		ai[niv][++k]=ai[niv+1][i];
	for (;j<=dr;++j)
		ai[niv][++k]=ai[niv+1][j];
}

void normalizare()
{
	int i,j;
	for (i=1;i<=n;i++)
		v.push_back(make_pair(x[i],y[i]));
	sort(v.begin(),v.end());
	v.push_back(make_pair(0,0));
	for (i=n;i>=1;i--)
		v[i]=v[i-1];
}

void citire()
{
	int i;
	f>>n;
	for (i=1;i<=n;i++)
		f>>x[i]>>y[i];
	for (log=1<<20;log>n;log>>=1);
}
	

int main()
{
	int i,j;
	citire();
	normalizare();
	build(1,1,n);


		solve();
	
	return 0;
}