Cod sursa(job #870804)

Utilizator loginLogin Iustin Anca login Data 3 februarie 2013 22:32:44
Problema Zoo Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
# include <fstream>
# include <iostream>
# include <vector>
# include <algorithm>
# define DIM 100003
# define MAX 120000
# define pb push_back
# define mp make_pair
# define fs first
# define sc second
using namespace std;
int n, m, x[3*DIM], y[3*DIM], s[DIM], a[MAX], N;
vector< pair<int, int> >X, Y;
vector< pair<pair<int,int>, int> > P, A, B, C, D;

void read ()
{
	ifstream fin ("zoo.in");
	fin>>n;
	int x, y;
	for(int i=1;i<=n;++i)
	{
		fin>>x>>y;
		X.pb(mp(x, i));
		Y.pb(mp(y, i));
	}
	fin>>m;
	for(int i=1;i<=2*m;++i)
	{
		fin>>x>>y;
		X.pb(mp(x, n+i));
		Y.pb(mp(y, n+i));
	}
}

void uniform()
{
	sort(X.begin(),X.end());
	sort(Y.begin(),Y.end());
	
	N=0;
	for(int i=0;i<X.size();++i)
	{
		if (i==0 || X[i-1].fs!=X[i].fs)
			++N;
		x[X[i].sc] = N;
	}
	
	N=0;
	for(int i=0;i<Y.size();++i)
	{
		if (i==0 || Y[i-1].fs!=Y[i].fs)
			++N;
		y[Y[i].sc] = N;
	}
}

void upd (int p)
{
	while(p<=N)
	{
		++a[p];
		p+=p^(p&(p-1));
	}
}

int query (int p)
{
	int r = 0;
	while(p>0)
	{
		r+=a[p];
		p-=p^(p&(p-1));
	}
	return r;
}

void comp (vector< pair<pair<int,int>, int> >V, int &i, pair<pair<int,int>, int> P, int o, int ho)
{
	
}

void solve ()
{
	for(int i=1;i<=n;++i)
		P.pb(mp(mp(x[i],y[i]), i));
	for(int i=1;i<=m;++i)
	{
		int j = n+2*i-1;
		A.pb(mp(mp(x[j]-1,y[j]-1), i));
		B.pb(mp(mp(x[j+1], y[j+1]), i));
		C.pb(mp(mp(x[j]-1, y[j+1]), i));
		D.pb(mp(mp(x[j+1], y[j]-1), i));
	}
	
	sort(P.begin(),P.end());
	sort(A.begin(),A.end());
	sort(B.begin(),B.end());
	sort(C.begin(),C.end());
	sort(D.begin(),D.end());
	
	int a=0, b=0, c=0, d=0;
	
	for(vector< pair< pair<int,int>, int> >::iterator I=P.begin();I!=P.end();++I)
	{
		while(a<A.size() && A[a].fs<I->fs)
		{
			s[A[a].sc] += query(A[a].fs.sc);
			++a;
		}
		while(b<B.size() && B[b].fs<I->fs)
		{
			s[B[b].sc] += query(B[b].fs.sc);
			++b;
		}
		while(c<C.size() && C[c].fs<I->fs)
		{
			s[C[c].sc] -= query(C[c].fs.sc);
			++c;
		}

		while(d<D.size() && D[d].fs<I->fs)
		{
			s[D[d].sc] -= query(D[d].fs.sc);
			++d;
		}
		
		upd(I->fs.sc);
	}
	while(a<A.size())
	{
		s[A[a].sc] += query(A[a].fs.sc);
		++a;
	}
	while(b<B.size())
	{
		s[B[b].sc] += query(B[b].fs.sc);
		++b;
	}
	while(c<C.size())
	{
		s[C[c].sc] -= query(C[c].fs.sc);
		++c;
	}

	while(d<D.size())
	{
		s[D[d].sc] -= query(D[d].fs.sc);
		++d;
	}
}

int main ()
{
	read ();
	uniform ();
	solve ();
	
	freopen("zoo.out", "w", stdout);
	for(int i=1;i<=m;++i)
		printf("%d\n", s[i]);
		
	return 0;
}