Cod sursa(job #452625)

Utilizator radu_voroneanuVoroneanu Radu Stefan radu_voroneanu Data 10 mai 2010 18:11:28
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.94 kb
#include <stdio.h>
#include <algorithm>
#define MAXM 100005
#define MAXN 16005
#define x first
#define y second
#define INF 2100000000
#define BIT(x) (((x)&((x)-1))^(x))

using namespace std;

pair<int, int> a[MAXN], c[MAXM*4];
int b[MAXN*2], d[MAXM*4], AIB[2*MAXN], Rasp[MAXM];
int X,Ans,i,st,dr,mij,T,N,M,W,poz,j,logT,lg;

inline void BinSearch()
{
	Ans = T;
	for (lg = logT; lg; lg>>=1)
		if (lg<Ans && b[Ans-lg]>=X)
			Ans -= lg;
}

inline void update(int x)
{
	int i;
	for (i=x; i<=T; i+=BIT(i))
		AIB[i]++;
}

inline int sum(int x)
{
	int i,s=0;
	for (i=x; i>0; i-=BIT(i))
		s += AIB[i];
	return s;
}

inline bool cmp(const int &a, const int &b)
{
	return (c[a].x<c[b].x);
}


int main()
{
	freopen("zoo.in","r",stdin);
	freopen("zoo.out","w",stdout);
	scanf("%d\n",&N);
	for (i=1; i<=N; i++){
		int x1,x2;
		char s[100];
		int poz, semn;
		fgets(s, 100, stdin);
		poz=-1; x1=x2=0;

		poz++;
		if (s[poz]=='-') semn = -1,poz++; else semn =1;
		for (; s[poz]>='0'; poz++) x1 = x1*10+s[poz]-'0';
		x1*=semn;

		poz++;
		if (s[poz]=='-') semn = -1, poz++; else semn =1;
		for (; s[poz]>='0'; poz++) x2 = x2*10+s[poz]-'0';
		x2*=semn;

		a[i].x =x1;  a[i].y = x2;
		b[2*i-1] = a[i].x;
		b[2*i]   = a[i].y;
	}
	sort(a+1, a+N+1);
	T = N<<1;
	b[++T] = INF;
	b[++T] = -INF;
	sort(b+1,b+T+1);
	int last = 1;
	for (i=2; i<=T; i++)
		if (b[i]!=b[last])
			b[++last] = b[i];
	T = last;

	for (logT=1; logT<=T; logT<<=1);

	for (i=1; i<=N; i++){
		X = a[i].x; BinSearch(); a[i].x = Ans;
		X = a[i].y; BinSearch(); a[i].y = Ans;
 	}

	scanf("%d\n",&M);

	W = 0;
	for (i=1; i<=M; i++){
		int x1,y1,x2,y2;
		x1=x2=y1=y2=0;
		char s[100];
		fgets(s,100,stdin);
		int semn =1;
		poz =-1;
		poz++;
		if (s[poz]=='-') semn = -1, poz++; else semn =1;
		for (; s[poz]>='0'; poz++) x1 = x1*10+s[poz]-'0';
		x1*=semn;

		poz++;
		if (s[poz]=='-') semn = -1, poz++; else semn =1;
		for (; s[poz]>='0'; poz++) y1 = y1*10+s[poz]-'0';
		y1*=semn;

		poz++;
		if (s[poz]=='-') semn = -1, poz++; else semn =1;
		for (; s[poz]>='0'; poz++) x2 = x2*10+s[poz]-'0';
		x2*=semn;

		poz++;
		if (s[poz]=='-') semn = -1, poz++; else semn =1;
		for (; s[poz]>='0'; poz++) y2 = y2*10+s[poz]-'0';
		y2*=semn;

		X = x1; BinSearch(); x1 = Ans;
		X = x2; BinSearch(); x2 = (x2==b[Ans])? Ans : Ans-1;  
		X = y1; BinSearch(); y1 = Ans;
		X = y2; BinSearch(); y2 = (y2==b[Ans])? Ans : Ans-1;
		c[++W] = make_pair(x2,y2);
		c[++W] = make_pair(x2,y1-1);
		c[++W] = make_pair(x1-1,y2);
		c[++W] = make_pair(x1-1,y1-1);
  	}

	for (i=1; i<=W; i++)
		d[i] = i;
	sort(d+1,d+W+1,cmp);

	a[N+1].x = INF;
	j = 1;
	for (i=1; i<=W; i++){
		int x1,y1;
		poz = d[i];
		x1 = c[poz].x;
		y1 = c[poz].y;
		for (; a[j].x<=x1; j++)
			update(a[j].y);
		int rez = sum(y1);
		if ((poz&3) == 2 || (poz&3) == 3) rez = -rez;
		Rasp[(poz-1)>>2] += rez;
	}
	
	for (i=1; i<=M; i++)
		printf("%d\n", Rasp[i-1]);

	return 0;
}