Cod sursa(job #870863)

Utilizator loginLogin Iustin Anca login Data 4 februarie 2013 02:20:27
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.52 kb
# include <fstream>
# include <iostream>
# include <algorithm>
# define DIM 100003
# define MAX 20000
using namespace std;
struct pct{
	int x, y, t;
	inline friend bool operator < (const pct &a, const pct &b) {
		if (a.x<b.x || (a.x==b.x && a.y<b.y) || (a.x==b.x && a.y==b.y && a.t<b.t))return true;
		return false;
	}
}v[5*DIM];

int n, m, s[DIM], a[MAX], y[MAX], N, Q;

void read ()
{
	ifstream fin ("zoo.in");
	fin>>n;
	for(int i=1;i<=n;++i)
	{
		fin>>v[i].x>>v[i].y;
		y[i+5]=v[i].y;
	}
	fin>>m;
	N=n;
	int x1, x2, y1, y2;
	for(int i=1;i<=m;++i)
	{
		fin>>x1>>y1>>x2>>y2;
		--x1;--y1;
		v[N+1].x=x1;v[N+1].y=y1;v[N+1].t=2*i;
		v[N+2].x=x2;v[N+2].y=y2;v[N+2].t=2*i;
		v[N+3].x=x1;v[N+3].y=y2;v[N+3].t=2*i+1;
		v[N+4].x=x2;v[N+4].y=y1;v[N+4].t=2*i+1;
		N+=4;
	}
}

void upd (int p)
{
	while(p<=Q)
	{
		++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;
}

int poz (int Y)
{
	int r=0;
	for(int st=1, dr=Q, mij=(st+dr)>>1;st<=dr;mij=(st+dr)>>1)
		if (y[mij]==Y)
			return mij;
		else if (y[mij]<Y)
		{
			r=mij;
			st=mij+1;
		}
		else
			dr=mij-1;
	return r;
}		

void solve ()
{
	sort(y+6, y+n+6);
	for(int i=1;i<=n;++i)
		if(i==1 || y[i+4]!=y[i+5])
			y[++Q]=y[i+5];			
	
	sort(v+1, v+N+1);
	
	for(int i=1;i<=N;++i)
		if (!v[i].t)
			upd(poz(v[i].y));
		else
		{
			int q = v[i].t>>1;
			s[q] += (q+q==v[i].t?1:-1) * query(poz(v[i].y));
		}
}

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