Cod sursa(job #25557)

Utilizator megabyteBarsan Paul megabyte Data 4 martie 2007 12:55:19
Problema Ograzi Scor 0
Compilator cpp Status done
Runda preONI 2007, Runda 3, Clasele 11-12 Marime 2.47 kb
#include <cstdio>
#define SEGT 2000002
#define NMAX 50002
#define MMAX 100002
#define INF "ograzi.in"
#define OUF "ograzi.out"
struct cord
{
	int x,y;
}pt[NMAX],sheep[MMAX];
int seg[SEGT]={0},a,b;
void qsort_byx(cord *a,int li,int ls)
{
	int i,j,piv;
	cord aux;
	i=li;j=ls;piv=a[i].x;
	do
	{
		while(a[i].x<piv) i++;
		while(a[j].x>piv) j--;
		if(i<=j)
		{
			aux=a[i];a[i]=a[j];a[j]=aux;
			i++;j--;
		}
	}while(i<j);
	if(i<ls) qsort_byx(a,i,ls);
	if(j>li) qsort_byx(a,li,j);
}
void insert(int nod,int li,int ls)
{
    if(a<=li&&ls<=b) seg[nod]++;
    else
    {
	    int mij;
	    mij=(li+ls)/2;
	    if(a<=mij) insert(2*nod,li,mij);
	    if(b>mij) insert(2*nod+1,mij+1,ls);
	    seg[nod]++;
    }
}
void extract(int nod,int li,int ls)
{
	if(a<=li&&ls<=b) seg[nod]--;
	else
	{
		int mij;
		mij=(li+ls)/2;
		if(a<=mij) extract(2*nod,li,mij);
		if(b>mij) extract(2*nod+1,mij+1,ls);
		seg[nod]--;
	}
}
int query(int nod,int li,int ls)
{
	if(a<=li&&ls<=b) return seg[nod];
	else
	{
		int mij,rez=0;
		mij=(li+ls)/2;
		if(a<=mij) rez+=query(2*nod,li,mij);
		if(b>mij) rez+=query(2*nod+1,mij+1,ls);
		return rez;
	}
}
int main()
{
	FILE *in,*out;
	int i,j,lo,hi,n,m,w,h,lim,total=0,k,ymax=0;
	in=fopen(INF,"r");
	out=fopen(OUF,"w");
	fscanf(in,"%d %d %d %d",&n,&m,&w,&h);
	for(i=1;i<=n;i++) fscanf(in,"%d %d",&pt[i].x,&pt[i].y);
	for(i=1;i<=m;i++)
	{
		fscanf(in,"%d %d",&sheep[i].x,&sheep[i].y);
		if(ymax<sheep[i].y+1) ymax=sheep[i].y+1;
	}
	qsort_byx(pt,1,n);
	qsort_byx(sheep,1,m);
	lo=hi=1;j=1;lim=0;
//	for(i=1;i<=n;i++) printf("%d ",pt[i].x);
//	printf("\n");
//	for(i=1;i<=m;i++) printf("%d ",sheep[i].x);
	while(sheep[j].x<pt[1].x)
	{
		j++;
		lim++;
	}
	lo=lim+1;
        //printf("%d\n",lo);
	for(i=1;i<n;i++)
	{
		hi=pt[i].x+w;
		lim=j-1;
		//while(k>=lo){ a=b=sheep[j].y+1; extract(1,1,ymax);k--;printf("%d ",k+1); }
		
		while(j<=m&&sheep[j].x<=hi) 
		{
			a=b=sheep[j].y+1;insert(1,1,ymax);
			//printf("%d ",j);
			j++;
		}
		a=pt[i].y+1;b=pt[i].y+h+1;
		total+=query(1,1,ymax);//printf("%d\n",total);
		k=lim;//printf("D: %d %d\n",lo,lim);
                while(k>=lo)
		{ 
			a=b=sheep[k].y+1;
		       if(pt[i+1].x>sheep[k].x)	extract(1,1,ymax);k--;//printf("%d ",k+1); 
		}
		lo=lim;

		
	}
	//printf("%d\n%d\n",hi,sheep[j].x);
	//for(i=1;i<2*ymax;i++) printf("%d ",seg[i]);
	//printf("%d %d\n",lo,j);
	hi=pt[i].x+w;
	while(j<=m&&sheep[j].x<=hi) 
	{
		a=b=sheep[j].y+1;insert(1,1,ymax);
		j++;
	}
	a=pt[i].y+1;b=pt[i].y+h+1;
	total+=query(1,1,ymax);
	fprintf(out,"%d",total);
	fclose(in);fclose(out);
	return 0;
}