Cod sursa(job #1181030)

Utilizator IonMosnoiIon Mosnoi IonMosnoi Data 1 mai 2014 17:42:20
Problema Ograzi Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.11 kb
#include<fstream>
#include<algorithm>
#include<vector>
using namespace std;
ifstream fi("ograzi.in");
ofstream fo("ograzi.out");
int H,W,m,n,y[100010],x[100010],dx[50100],dy[50100];
vector <int> puncte[200000];
void sortq(int l,int r){
	int m=x[(l+r)/2],i=l,j=r;
	do{
		while(m>x[i])i++;
		while(m<x[j])j--;
		if(i<=j){
			swap(x[i],x[j]);
			swap(y[i],y[j]);
			i++;
			j--;
		}
	}while(i<=j);
	if(i<r)sortq(i,r);
	if(j>l)sortq(l,j);
}
void create(int l=1,int r=m,int nod=1){
	if(l==r){
		puncte[nod].push_back(l);
		return;
	}
	create(l,(l+r)/2,nod*2);
	create((l+r)/2+1,r,nod*2+1);
	int i=0,j=0;
	while(i<puncte[nod*2].size() || j<puncte[nod*2+1].size()){
		if(i==puncte[nod*2].size()){
			puncte[nod].push_back(puncte[nod*2+1][j]);
			j++;
		}else if(j==puncte[nod*2+1].size()){
			puncte[nod].push_back(puncte[nod*2][i]);
			i++;
		}else{
			if(y[puncte[nod*2][i]]<y[puncte[nod*2+1][j]]){
				puncte[nod].push_back(puncte[nod*2][i]);
			    i++;
			}else{
				puncte[nod].push_back(puncte[nod*2+1][j]);
			    j++;
			}
		}
	}
}

int lbsearch(int v,int l=1,int r=m){
	if(x[l]>=v)return l;
	if(x[r]<v)return -1;
	if(r==l)return l;
	int mij = (l+r)/2;
	if(x[mij]>=v)return lbsearch(v,l,mij);
	return lbsearch(v,mij+1,r);
}
int rbsearch(int v,int l=1,int r=m){
	if(x[l]>v)return -1;
	if(x[r]<=v)return r;
	if(r==l)return l;
	int mij = (l+r)/2;
	if(x[mij+1]<=v)return rbsearch(v,mij+1,r);
	return rbsearch(v,l,mij);
}
int lbsearch1(int v,int l,int r,int nr){
	if(y[puncte[nr][l]]>=v)return l;
	if(y[puncte[nr][r]]<v)return -1;
	if(r==l)return l;
	int mij = (l+r)/2;
	if(y[puncte[nr][mij]]>=v)return lbsearch1(v,l,mij,nr);
	return lbsearch1(v,mij+1,r,nr);
}
int rbsearch1(int v,int l,int r,int nr){
	if(y[puncte[nr][l]]>v)return -1;
	if(y[puncte[nr][r]]<=v)return r;
	if(r==l)return l;
	int mij = (l+r)/2;
	if(y[puncte[nr][mij+1]]<=v)return rbsearch1(v,mij+1,r,nr);
	return rbsearch1(v,l,mij,nr);
}
int query(int ymin,int ymax,int a,int b,int l=1,int r=m,int nod =1){
	int sol = 0;
	if(a<=l && b>=r){
	/*	for(int i=0;i<puncte[nod].size();i++)
		 if(ymin<=y[puncte[nod][i]] && ymax>=y[puncte[nod][i]])sol++;	
		 return sol;	*/
		 int r1 = rbsearch1(ymax,0,puncte[nod].size()-1,nod),l1=lbsearch1(ymin,0,puncte[nod].size()-1,nod);
		 if(l1==-1 || r1==-1)return 0;
		 else return r1-l1+1;
	}
	int mij = (r+l)/2;
	if(b>=mij+1)sol+=query(ymin,ymax,a,b,mij+1,r,nod*2+1);
	if(a<=mij)sol+=query(ymin,ymax,a,b,l,mij,nod*2);
	return sol;
}
int main(){
	fi>>n>>m>>W>>H;
	for(int i=1;i<=n;i++)fi>>dx[i]>>dy[i];
	for(int i=1;i<=m;i++)fi>>x[i]>>y[i];
	sortq(1,m);
	for(int i=1;i<=m&&0 ;i++)fo<<i<<"- "<<x[i]<<" "<<y[i]<<endl;
	create();
	for(int i=1;i<=7 && 0;i++){
		fo<<i<<"| ";
		for(int j=0;j<puncte[i].size();j++)fo<<puncte[i][j]<<" ";
		fo<<endl;
	}
	
	int sol = 0,l,r;
	for(int i=1;i<=n ;i++){
		l = lbsearch(dx[i]);
		r = rbsearch(dx[i]+W);
	//	fo<<l<<" "<<r<<" "<<endl;
	if(l!=-1 && r!=-1)	
sol += query(dy[i],dy[i]+H,l,r);
//for(int j=l;j<=r;j++)if(y[j]>=dy[i]&&y[j]<=dy[i]+H)sol++;
	//	fo<<sol<<" "<<dy[i]<<" "<<dy[i]+H<<" "<<endl;
	}
	//fo<<rbsearch(5);
	fo<<sol;	
}