Cod sursa(job #870843)

Utilizator loginLogin Iustin Anca login Data 3 februarie 2013 23:59:42
Problema Zoo Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
# include <fstream>
# include <iostream>
# include <vector>
# include <algorithm>
# define DIM 100303
# define MAX 120000
# define H 666013
# 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, M, xx;
vector< pair<int, int> >X[H+3], Y[H+3], P, A[MAX], B[MAX], C[MAX], D[MAX];

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

void uniform()
{
	M=0;
	for(int h=0;h<H;++h)
	{
		int sz = X[h].size();
		for(int i=0;i<sz;++i)
		{
			x[X[h][i].sc]=++M;
			for(int j=i+1;j<sz;++j)
				if (X[h][j].fs==X[h][i].fs)
				{
					x[X[h][j].sc]=M;
					X[h][j]=X[h][sz-1];
					--j;
					--sz;
				}
		}
	}
	
	N=0;
	for(int h=0;h<H;++h)
	{
		int sz = Y[h].size();
		for(int i=0;i<sz;++i)
		{
			y[Y[h][i].sc]=++N;
			for(int j=i+1;j<sz;++j)
				if (Y[h][j].fs==Y[h][i].fs)
				{
					y[Y[h][j].sc]=N;
					Y[h][j]=Y[h][sz-1];
					--j;
					--sz;
				}
		}
	}
}

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(int xxx)
{
	while(xx<=xxx)
	{
		for(vector< pair<int,int> >::iterator I=A[xx].begin();I!=A[xx].end();++I)
			s[I->sc]+=query(I->fs);
		for(vector< pair<int,int> >::iterator I=B[xx].begin();I!=B[xx].end();++I)
			s[I->sc]+=query(I->fs);
		for(vector< pair<int,int> >::iterator I=C[xx].begin();I!=C[xx].end();++I)
			s[I->sc]-=query(I->fs);
		for(vector< pair<int,int> >::iterator I=D[xx].begin();I!=D[xx].end();++I)
			s[I->sc]-=query(I->fs);
		++xx;
	}
}	

void solve ()
{
	for(int i=1;i<=n;++i)
		P.pb(mp(x[i],y[i]));
	for(int i=1;i<=m;++i)
	{
		int j = n+2*i-1;
		A[x[j]-1].pb(mp(y[j]-1, i));
		B[x[j+1]].pb(mp(y[j+1], i));
		C[x[j]-1].pb(mp(y[j+1], i));
		D[x[j+1]].pb(mp(y[j]-1, i));
	}
	
	sort(P.begin(),P.end());
	
	comp(P[0].fs - 1);
	for(int i=0;i<P.size();++i)
	{
		if (i>0 && P[i-1].fs != P[i].fs)
			comp(P[i-1].fs);
		upd(P[i].sc);
	}
	comp(M);
}

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