Cod sursa(job #833073)

Utilizator BalcauIonutFMI-Balcau Ionut BalcauIonut Data 11 decembrie 2012 21:08:06
Problema Zoo Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include<iostream>
#include<vector>
#include<fstream>
#include<algorithm>
using namespace std;

vector< pair<int,int> > v;
vector<int> t[50000];
int n,l,r,yl,yr,sum;

void buildTree(int nod, int left, int right){
	if(left==right){
		t[nod].push_back(0);
		t[nod].push_back(v[left].second);
		// cout<<nod<<':'<<left<<'-'<<right<<"->";
		// cout<<t[nod][0]<<'\n';
		return;
	}
	int mij=(left+right)/2;
	buildTree(nod*2,left,mij);
	buildTree(nod*2+1,mij+1,right);
	t[nod].push_back(0);
	t[nod].resize(t[nod*2+1].size()+t[nod*2].size()-1);
	merge(t[nod*2].begin()+1,t[nod*2].end(),t[nod*2+1].begin()+1,t[nod*2+1].end(),t[nod].begin()+1);

	// vector<int>::iterator it;
	// cout<<nod<<':'<<left<<'-'<<right<<"->";
	// for(it=t[nod].begin();it!=t[nod].end();++it)
	// 	cout<<*it<<' ';
	// cout<<'\n';
}


int qMin(int x){

	int left=1,right=n,mij,k=-1;;
	while(left<right){
		mij=(left+right)/2;
		if(x==v[mij].first){
			right=mij-1; k=mij;
			continue;
		}
		if(x<v[mij].first)
			right=mij-1;
		else
			left=mij+1;
	}
	if(k>0) return k;
	return left;
}

int qMax(int x){
	int left=l,right=n,mij,k=-1;
	while(left<right){
		mij=(left+right)/2;
		if(x==v[mij].first){
			left=mij+1; k=mij;
			continue;
		}
		if(x>v[mij].first)
			left=mij+1;
		else
			right=mij-1;
	}
	if(k>0) return k;
	return right;
}

int rez(int x){
	int left,right,mij,r,k;
	left=1; right=t[x].size()-1; k=-1;
	while(left<right){
		mij=(left+right)/2;
		if(yl==t[x][mij]){
			right=mij-1; k=mij;
			continue;
		}
		if(yl<t[x][mij])
			right=mij-1;
		else
			left=mij+1;
	}
	if(k>0) left=k;
	r=left;

	right=t[x].size()-1; k=-1;
	while(left<right){
		mij=(left+right)/2;
		if(yr==t[x][mij]){
			left=mij+1; k=mij; 
			continue;
		}
		if(yr>t[x][mij])
			left=mij+1;
		else
			right=mij-1;
	}
	if(k>0) return k-r+1;
	return right-r+1;
}

void query(int nod, int left, int right){
	if(l<=left && right<=r){
		sum+=rez(nod);
		return;
	}
	int mij=(left+right)/2;
	if(l<=mij) query(nod*2,left,mij);
	if(r>mij) query(nod*2+1,mij+1,right);
}

int main(){
	ifstream fin("zoo.in");
	ofstream fout("zoo.out");
	fin>>n;
	pair<int,int> x;
	int i; v.push_back(x);
	for(i=0;i<n;++i){
		fin>>x.first>>x.second;
		v.push_back(x);
	}
	sort(v.begin()+1,v.end());
	buildTree(1,1,n);	
	
	int m;
	pair<int,int> a,b;
	
	fin>>m;
	for(i=0;i<m;++i){
		fin>>a.first>>a.second>>b.first>>b.second;
	
		l=qMin(a.first); yl=a.second;
		r=qMax(b.first); yr=b.second;
		
		// cout<<l<<' ';
		// cout<<' '<<r<<'\n';


		sum=0;
		query(1,1,n);
		fout<<sum<<  '\n';
	//	cout<<sum<<'\n';
	}


	// vector< pair<int,int> >::iterator it;
	// for(it=v.begin();it!=v.end();++it){
	// 	cout<<it->first<<','<<it->second<<' ';
	// }



	return 0;
}