Cod sursa(job #3225631)

Utilizator DumitrescuADumitrescuA DumitrescuA Data 18 aprilie 2024 11:16:02
Problema Zoo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.18 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

ifstream cin("zoo.in");
ofstream cout("zoo.out");

pair<int,int> v[16005];
vector<int> aint[70005];
int x1,x2,y1,y2;

void init(int nod,int st,int dr){
    int i;
	for(i=st;i<=dr;i++) aint[nod].push_back(v[i].second);
	sort(aint[nod].begin(),aint[nod].end());
	if(st==dr) return;
	int put=(nod<<1),mij=(st+dr)/2;
	init(put,st,mij);
	init(put+1,mij+1,dr);
}

int query(int nod,int st,int dr,int qst,int qdr) {
	int put=(nod<<1),mij=(st+dr)/2,rasp=0;
	if(st>=qst && dr<=qdr)
		return upper_bound(aint[nod].begin(),aint[nod].end(),y2)-lower_bound(aint[nod].begin(),aint[nod].end(),y1);
	if(mij>=qst)
		rasp+=query(put,st,mij,qst,qdr);
	if(mij<qdr)
		rasp+=query(put+1,mij+1,dr,qst,qdr);
	return rasp;
}

int main()
{
    int n,m,st,dr,i;
    cin>>n;
    for(i=1;i<=n;i++)
        cin>>v[i].first>>v[i].second;
    sort(v+1,v+n+1);
    init(1,1,n);
	cin>>m;
	for(i=1;i<=m;++i) {
		cin>>x1>>y1>>x2>>y2;
		st=lower_bound(v+1,v+n+1,make_pair(x1,y1))-v;
		dr=upper_bound(v+1,v+n+1,make_pair(x2,y2))-v-1;
		if(st>dr) cout<<"0\n";
		else cout<<query(1,1,n,st,dr)<<"\n";
	}
    return 0;
}