Cod sursa(job #870860)

Utilizator loginLogin Iustin Anca login Data 4 februarie 2013 02:06:38
Problema Zoo Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
# include <fstream>
# include <iostream>
# include <algorithm>
# define DIM 100003
# define MAX 20000
using namespace std;
struct pct{
	int x, y, t;
	pct(){}
	pct(int X, int Y, int T) {
		x=X;y=Y;t=T;}
	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], p[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]=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=n, mij=(st+dr)/2;st<=dr;mij=(st+dr)/2)
		if (y[mij]==Y)
			return p[mij];
		else if (y[mij]<Y)
		{
			r=p[mij];
			st=mij+1;
		}
		else
			dr=mij-1;
	return r;
}		

void solve ()
{
	sort(y+1, y+n+1);
	for(int i=1;i<=n;++i)
	{
		if(i==1 || y[i-1]!=y[i])
			++Q;
		p[i]=Q;
	}
	
	sort(v+1, v+N+1);
	
	for(int i=1;i<=N;++i)
		if (!v[i].t)
			upd(poz(v[i].y));
		else
			s[v[i].t/2] += (v[i].t%2?-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;
}