Cod sursa(job #288177)

Utilizator FlorianFlorian Marcu Florian Data 25 martie 2009 16:56:13
Problema Zoo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.25 kb
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX_N 16002
#define pb push_back
#define x first
#define y second
vector <int> H[4*MAX_N+3];
pair <int,int> P[MAX_N];
int N,M;
int x1,x2,y2,y1;
int sol;
void read()
 {
	  freopen("zoo.in","r",stdin);
	  freopen("zoo.out","w",stdout);
	  scanf("%d",&N);
	  int i,X,Y;
	  for(i=1;i<=N;++i)
		{ 
			scanf("%d %d",&X,&Y);
			P[i].first = X; P[i].second = Y;
	    }
 }
void merge(int n)
{
	int fs=2*n, fd=2*n+1;
	// H[n] = H[fs] + H[fd] ;
	int i=0, j=0;
	int l1 = H[fs].size();
	int l2 = H[fd].size();
	while(i<l1 && j<l2)
	{
		if(H[fs][i] < H[fd][j]){ H[n].pb(H[fs][i]); ++i; }
		else if(H[fs][i] > H[fd][j]) { H[n].pb(H[fd][j]); ++j; }
		else { H[n].pb(H[fd][j]); H[n].pb(H[fd][j]); ++i; ++j;}
	}
	while(i<l1) { H[n].pb(H[fs][i]); ++i; }
	while(j<l2) { H[n].pb(H[fd][j]); ++j; }
}

void build(int n, int l, int r)
 {
	 if(l==r)
	 {
		 H[n].pb(P[r].y);
		 //print(n);
		 return;
	 }
	 int m=(l+r)/2, fs=2*n, fd=2*n+1;
	 build(fs, l, m);
	 build(fd,m+1,r);
	 
	 merge(n);
	 //print(n);
 }
int nr_puncte(int n, int y1, int y2)
 {
	 int m,i,j;
	 int s1=0, s2=0;
	 if(H[n][0] > y2) return 0;
	 if(H[n][H[n].size()-1] < y1) return 0;
	 i=0; j=H[n].size()-1;
	 while(i<=j)
	 {
		 m=(i+j)/2;
		 if(H[n][m] < y1 ) i=m+1;
		 else {
			 if(m==0) break;
			 else if(H[n][m-1] < y1) break;
		     else j=m-1;
		 }
	 }
	 if(i>j) return 0;
	 s1 = m;
	 i=0; j=H[n].size()-1;
	 int l = H[n].size();
	 while(i<=j)
	 {
		 m=(i+j)/2;
		 if(H[n][m] > y2) j=m-1;
		 else 
			 {
				 if(m == l-1) break;
				 if(H[n][m+1] > y2) break;
			     i=m+1;
			 }
	 }
	 s2=m;
	 if(i>j) return 0;
	 return s2-s1+1;
}
void query(int n, int l, int r) // vad cate pcte exista in dreptunghiul (x1,y1,x2,y2)
 {
	 if(x1<=P[l].x && P[r].x<=x2)
	 {
		 sol += nr_puncte(n, y1, y2);
		 return;
	 }
	 else if(l!=r){
	 int m=(l+r)/2, fs=2*n, fd=2*n+1;
	 if(x1<=P[m].x) query(fs,l,m);
	 if(x2>=P[m+1].x) query(fd,m+1,r);}
 }
void solve()
{
	scanf("%d",&M);
	while(M--)
	{
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		sol=0;
		query(1,1,N);
		printf("%d\n",sol);
	}
 }
int main()
{
	read();
	sort(P+1,P+N+1);
	build(1,1,N);
	solve();
	return 0;
}