Cod sursa(job #79763)

Utilizator gigi_becaliGigi Becali gigi_becali Data 23 august 2007 19:38:13
Problema Ograzi Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.28 kb
using namespace std;
#include <cstdio>
#include <string>
#include <cstdlib>
#include <algorithm>
#define left(i) ( (i)<<1 )
#define right(i) ( ((i)<<1)|1)
struct nod{ int x, y;};

nod dr[50001], a[100001];
int N, M, W, H;
int *x[200001];
int len[200001];
int x1, y1, x2, y2;
struct cmp{
	bool operator()(const nod &a, const nod &b)const 
	{
		if(a.x<b.x)return 1;
		if(a.x==b.x)if(a.y<b.y)return 1;
		return 0;
	}
};

void read()
{
	freopen("ograzi.in","r",stdin);
	scanf("%d %d %d %d\n", &N, &M, &W, &H);
	int i;
	for(i=1;i<=N;++i) scanf("%d %d\n", &dr[i].x, &dr[i].y);
	for(i=1;i<=M;++i) scanf("%d %d\n", &a[i].x, &a[i].y);
	sort(a+1, a+M+1,cmp());
}

void build(int n, int l, int r)
{
	if(l==r) { x[n]=(int*)malloc(sizeof(int)*3);; x[n][len[n]++]=a[l].y;return;}
	int m=(l+r)>>1;
	build(left(n), l, m); build(right(n), m+1, r);
	
	int i,j, N=len[left(n)], M=len[right(n)];
	x[n]=(int*)malloc(sizeof(int)*(N+M+3));
	for(i=0, j=0;i<N && j<M;)
		if(x[left(n)][i]>x[right(n)][j]) x[n][len[n]++]=x[right(n)][j++];
			else						 x[n][len[n]++]=x[left(n)][i++];
	
	for(;i<N;++i) x[n][len[n]++]=x[left(n)][i];
	for(;j<M;++j) x[n][len[n]++]=x[right(n)][j];
}

inline int bsearch(int a[], int n)
{
	int i, cnt,pi, pj;
	for(i=0, cnt=(1<<20); cnt ; cnt>>=1)
		if(i+cnt<n)
			if(a[i+cnt]<=y2) i+=cnt;
	pj=i;
			
	for(i=n-1, cnt=(1<<20); cnt ; cnt>>=1)
		if(i-cnt>=0)
			if(a[i-cnt]>=y1) i-=cnt;
	pi=i;
	return pj-pi+1;
}


int query(int n, int l, int r) //x1, x2,y1, y2
{
	if(x1<=l && r<=x2) 
	{
		if(x[n][0]>y2 || x[n][len[n]-1]<y1) return 0;
		if(x[n][0]>=y1 && x[n][len[n]-1]<=y2) return (r-l+1);
		return bsearch(x[n], len[n]);
	}
	int m=(l+r)>>1;
	int s=0;
	if(x1<=m) s+=query(left(n), l, m);
	if(x2>m) s+=query(right(n), m+1, r);
	return s;
}


int main()
{
	freopen("ograzi.out","w",stdout);
	read();
	int i, j, cnt;
//	for(i=1;i<=M;++i) printf("%d %d\n", a[i].x, a[i].y);
	build(1, 1, M);
	
	int nr=0;
	
	for(i=1;i<=N;++i)
	{
		x1=dr[i].x;
		x2=x1+W;
		y1=dr[i].y;
		y2=y1+H;
		
		for(j=1, cnt=(1<<20);cnt;cnt>>=1)
			if(j+cnt<=M)
				if(a[j+cnt].x<=x2)j+=cnt;
		x2=j;
				
		for(j=M, cnt=(1<<20);cnt;cnt>>=1)
			if(j-cnt>=1)
				if(a[j-cnt].x>=x1)j-=cnt;
		x1=j;
		nr+=query(1, 1, M);
	
	}
	printf("%d\n", nr);
	
	return 0;
}